移动网络中基于概率的拓扑控制

1、移动无线传感器网络中基于概率的最大权控制集钟海洋 禹继国摘要：本文给出了一种在移动无线传感器网络中构造最大权控制集的近似算法，并证明了当网络中的最小权顶点覆盖与最大权控制集的权值之比很小的时候，我们算法的近似因子是十分接近1的。关键词：移动无线传感器网络（MWSN）；最小权顶点覆盖；最大权控制集。1 引言 2 准备工作为了描述的方便，我们先给出一些符号的定义如下表：表示两个节点移动圆形区域的两个圆心之间的距离表示节点i移动圆形区域的半径表示两个节点之间的最大距离表示节点的传输半径表示节点i在它移动区域内能和节点j通信的部分的面积表示节点i在内的概率表示节点i和节点j通信的概率我们假设所有的传感

2、器节点在一个已知圆心和半径的圆形区域内移动，传感器节点出现在区域内任何一点的概率是相同的。这样，两个节点之间的最远距离就等于他们两个运动区域的圆心之间的距离加上各自半径的距离。比如节点i和节点j之间的最大的距离的计算公式是： （1）这里表示两个节点运动区域圆心之间的距离，表示节点i的所在区域的半径。计算出两个节点之间的最大距离，我们说，当两个节点之间的最大距离小于传输半径时，两个节点是可以直接通信的。但是，最大距离大于传输半径的一对节点不一定就不能通信，由于节点的移动性，两个节点有时也可能移动到彼此的通信范围内，我们看到下图，图1S(j,i)S(i,j)ij当两个节点同时在S(i,j)和S(j

3、,i)的时候是可以通信的。由图2我们可以得到的计算公式是： （2）这里，。图2ijRrjdij-riri我们把节点j出现在S(j,i)的概率记为，根据假设节点在自己的移动区域内任何一点出现的概率都是相同的，所以 （3）同理，节点i出现在S(i,j)部分的概率为： （4）这里，。所以两节点可以通信的概率为： （5） 这样，我们就得到了一个带权图G=(V,E,W)，V是所有传感器节点的集合，两个传感器可以通信他们之间就有一条边，E是所有边的集合，边上的权重表示的是两个传感器可以通信的概率。我们将每个节点关联的边上的所有权值加起来，将这个值作为这个节点的权值，于是我们就得到了一个节点带权图。下图就是

4、一个节点带权图的简单例子。从图中我们可以看出，一个节点的权重越大，这个节点就与他的邻居通信的可能性就越大，如果由这样的节点作为控制节节点，那么减少很多不必要的能量浪费，我们接下来的工作就是要构造一个权值最大的控制集。3 算法设计 我们算法的主要思想是，首先在这个图上构造一个权值最小的顶点覆盖，然后返回这些节点的补集，我们就得到一个权值最大的控制集。图G=(V,E)中的顶点覆盖时一个结合使得每一条边至少有一个端点在S中，现在我们考虑这个问题，每个顶点有一个权重，顶点集合S的权重记作，我们希望找到一个最小的顶点覆盖S。由于最小权值的顶点覆盖问题是一个NP完全的，所以我们用定价法来设计这个问题的近似

5、算法，现在假设图中的每一条边都有一个价格，如果对于每个顶点i，满足，则称价格是公平的。如果，则称顶点i是紧的。下面我们给出最小权值顶点覆盖的近似算法：对所有的，令While存在边e=(i,j)使得i和j都不是紧的 选择一条这样的边e 在不违反公平性的条件下加大EndWhile令S是所有紧顶点的集合Return S得到了一个最小权值顶点覆盖S以后，我们只要返回它的补集V-S，就得到了我们想要的最大权值控制集。所以最大权值控制集近似算法是：对所有的，令While存在边e=(i,j)使得i和j都不是紧的 选择一条这样的边e 在不违反公平性的条件下加大EndWhile令S是所有紧顶点的集合Return

6、 V-S4 算法分析接下来我们首先来证明我们算法得到的是一个权值最大的独立集，然后证明这个权值最大的独立集是一个极大独立集，由于极大独立集是一个控制集，所以我们就得到了一个权值最大的控制集。引理 1：顶点覆盖的补集是一个独立集。证明：如果S是一个顶点覆盖，考虑V-S中任意两个顶点u和v，如果他们之间有一条边e，那么e的两个端点度都不在S中，那么与S时一个顶点覆盖相矛盾。所以V-S是一个独立集。定理1：如果对一个顶点带权的图存在一个权值最小的顶点覆盖，那么这个权值最小的顶点覆盖的补集就是一个权值最大的独立集。证明：由引理1我们知道，顶点覆盖的补集是一个独立集，现在我们利用反证法来证明这个独立集的

7、权值最大性。假设这个独立集S的权值不是最大，那么必然会存在另一个更大的独立集S，由于整个网络的权值和是一个定值，我们假设它为W，那么,这样就存在一个权值更小的顶点覆盖，产生了矛盾。所以最小权值顶点覆盖的补集是一个最大权值独立集。定理 2：最大权值独立集是一个极大独立集。证明：采用反证法，假设最大权值独立集不是一个极大独立集，那么至少存在一个节点u,使得这个独立集S在加入u以后仍然是一个独立集，这样, 与最大权值相矛盾。所以最大权值独立集是一个极大独立集。定理 3：极大独立集是一个控制集。由上面得定理1-3可以得出，我们的算法确实返回了一个权值最大的控制集。定理 4：最大权控制集问题是NP完全的

8、。证明：最大权控制集的补集就是最小权顶点覆盖，我们很容易的可以把最大权控制集问题规约到最小权顶点覆盖问题，由于最小权顶点覆盖问题是NP完全的，所以最大权控制集问题也是NP完全的。由于最大权控制集问题是NP完全的，所以我们的算法也就是个近似算法，下面我们来看一下算法的近似因子。定理 5：假设最小权顶点覆盖与最大权控制集的权值之比不超过，我们的算法的近似因子为。证明：算法的前一部分是构造最小权值顶点覆盖的算法，它的近似因子2，现在我们假设算法返回最大权值控制集为S，最优值为S*，那么V-S就是最小权值顶点覆盖算法返回的顶点覆盖，V-S*就是最小权值顶点覆盖的最优值。因为最小权值顶点覆盖近似算法的近似因子是2，所以,由于整个图的权值总和是一个定值，我们用W来表示，则,因为，所以，我们令，这里表示近似因子，我们看不等式的后一部分，由我们可以得到,所以。根据我们的题设，最小权顶点覆盖与最大权控制集的权值之比是不超过的，显然这里，所以我们有，则。由上面的定理4我们可以看出，当一个图的最小权值顶点覆盖与最大权值控制集的权值之比非常小的时候，即非常小的时候，我们算法的近似因子是很接近1的，是一个很好的近似算法。5 结论本文我们给出了一个在移动无线传感器网络中构造最大权控制集