覆盖模型.ppt

《覆盖模型.ppt》由会员分享，可在线阅读，更多相关《覆盖模型.ppt（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、覆盖模型覆盖模型 1 覆盖模型覆盖模型是一类离散点选址模型。所谓覆盖模型，是对于需求已知的一些需求点，如何确定一组服务设施来满足这些需求点的需求。常用的有两类主要模型：集合覆盖模型，即用最小数量的设施去覆盖所有的需求点；最大覆盖模型，即在给定数量的设施去覆盖所有需求点。区别：集合覆盖模型要满足所有需求点的需求，而最大覆盖模型则只覆盖有限的需求点，两种模型的应用情况取决于服务设施的资源充足与否。2集合覆盖模型的构建第一步，找到每一个候选地址可以提供服务的所有需求点的集合 A(j),它们距离该候选地址的距离小于或者等于指定距离。第二步，找到可以给每一个需求点提供服务的所有候选地址的集合 B(i)，

2、一般说来，它与 A(j)是一样的，但是考虑他条件的限制，也有不一样的情况，这要视具体的情况而定。第三步，设变量 xij 1 表示位于 i 点的物流中心向位于 j点的需求点供货，否则 xij 0。yi 1 表示在 i 点建立物流中心，否则 yi=0。由于每个需求点都可以从一个或者多个物流中心进货，由此决定了物流服务分配的约束条件为,1，根据 B(i)可以写出各个约束条件。但是为了减少物流中心建设的成本，应该选取能够覆盖所有需求点的最小数量的候选地址的组合。第四步，检验。根据集合 A(j)，验证求得的物流中心选址是否覆盖了所有需求点。3实例在Ad-hoc传感器网络中，信号覆盖范围或覆盖率是衡量网络服务质量的主要度量指标。因此，如何在保证信号覆盖质量的前提下，尽可能地节省网络建设成本就显得格外重要1。如图1所示，四个平面上的圆形区域是同种型号的传感器 S1S4的信号覆盖范围，e1e9是九个服务客户，问：设置传感器的最佳方案是什么?4不妨将九个服务客户视为“元素”，而各传感器的信号覆盖范围内的元素（客户）分别构成集合：S1=e1，e2，e3，e4，e5S2=e3，e4，e5，e6，e7，e8S3=e2，e4，e5，e7，e8，e9S4=e1，e2，e3，e4，e8，e9则传感器的最佳设置方案应为集合 S=e1e9的一个基数最小的集合覆盖。5最大覆盖模型6