覆盖模型.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,覆盖模型,1,覆盖模型,覆盖模型是一类离散点选址模型。所谓覆盖模型，是对于需求已知的一些需求点，如何确定一组服务设施来满足这些需求点的需求。,常用的有两类主要模型：集合覆盖模型，即用最小数量的设施去覆盖所有的需求点；最大覆盖模型，即在给定数量的设施去覆盖所有需求点。,区别：集合覆盖模型要满足所有需求点的需求，而最大覆盖模型则只覆盖有限的需求点，两种模型的应用情况取决于服务设施的资源充足与否。,2,集合覆盖模型的构建,第一步，找到每一个候选地址可以提供服务的所有需求点,的集合 A(j),它们距离该候选地址的距离小于或者等于指定距,离。,第二步，找到可以给每一个需求点提供服务的所有候选地,址的集合 B(i)，一般说来，它与 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,，,e5,S2=e3,，,e4,，,e5,，,e6,，,e7,，,e8,S3=e2,，,e4,，,e5,，,e7,，,e8,，,e9,S4=e1,，,e2,，,e3,，,e4,，,e8,，,e9,则传感器的最佳设置方案应为集合 S=e1e9的一个基数,最小的集合覆盖。,5,最大覆盖模型,6,