三维无线移动传感器网络k-覆盖研究

摘要：考虑移动传感器的移动会大量消耗能量且比较昂贵，使用密度为O(k)的移动传感器来满足网络k-覆盖的密度需求，并给出了网络要达到k-覆盖传感器需移动的最大距离的一个界O((log L)1／3)；建立了三维网络传感器移动数学模型，将传感器重新部署问题转化为最大网络流问题，用分布式重新部署算法仿真证明了其有效性。
关键词：无线传感器网络；k-覆盖；最大移动距离；最大网络流算法

0 引言
    无线移动传感器网络是由能量有限且具有感知、计算和通信能力的微型移动传感器节点通过自组织的方式构成的无线网络。它不需要固定网络支持，具有快速展开，抗毁性强等特点，可广泛应用于军事、工业、交通、环保等领域。然而，由于传感器网络通常工作在复杂的环境下，而且网络中传感器节点众多，所以大都采用随机部署方式。而这种方式很难一次性将数日众多的传感器节点放置在适合的位置，极容易造成传感器网络覆盖的不合理。所以，在传感器网络部署初始，需要采用覆盖控制策略的重新部署，以获得理想的网络覆盖性能。其中满足k-覆盖是很多应用中需要重点考虑的。
    通常认为如果给定一个区域，若其中的任何一个点至少被k个传感器覆盖，则称此传感器网络达到k-覆盖。因为传感器是移动的，所以它们可以调整自己的位置，以冗余度O(1)达到k-覆盖。然而，由于移动消耗大量的能量，为节省能量，如何确定传感器的最大移动距离呢?前人对此曾做过大量工作。Wu J等人最小化了每个传感器的最大移动距离，但只号虑了二维网络。wang G等人通过级联式短距离移动虽然限制了每个传感器，但也没具体给出最大距离的一个界。因此，本文的研究目标是在三维无线传感器网络中，给出传感器移动的最大距离的一个界，在此前提下，用分布式重新部署算法实现网络k-覆盖，证实其有效性。

1 传感器的密度和移动距离
    假设移动传感器独立均匀分布于体积为L的立方体区域中，传感器的传感半径为r，k为网络覆盖因子。将体积为L的立方体分解成边长为的小立方体。显然，其中每个格点的密度为。当传感器移动到每个格点上时，移动传感器的密度Λ为，每个传感器的感应球域为，每个球域将含有个传感器，所以区域中仟何一个点将至少被k个传感器所覆盖，即网络达到k-覆盖。当传感器随机撒播在立方体区域中，传感器移动到每个格点的最大距离可以由以下定理得出。
    根据Ahuja RK给出的定理，将n个点均匀分布独立撒播在一个单位立方体中，将单位立方体分解成n个小立方体，则点和格点之间以最大概率存在完全匹配，且匹配的最大距离为O((log，n／n)1／3)。
    因这里考虑的是体积为L的立方体，由上述定理可得网络格点数目为 个。因此传感器移动的最大移动距离约为 。由此可见，移动传感器网络相对静态传感器网络能弥补节点分布的随机性。在覆盖过程中如果传感器全部是移动的，那么它可以通过移动一小段距离达到k-覆盖。相对静态传感器网络，随着出现网络规模的扩大，传感器的密度也会随着增大的倾向，而移动传感器网络的传感器密度却仍能保持不变，只需随着网络的增大，移动距离改变为O((log L)1／3)即可。

2 移动模型
    为了实现三维传感器网络k-覆盖，提出传感器移动策略问题如下：假设每个小立方体i含有mi个移动传感器，每个立方体i将有vi=k个空缺。将传感器移动问题转化为网络流问题，其中小立方体中多余的移动传感器(网络流)“流入”网络图中存在的空缺。
    构造一个以每个小立方体为顶点的图G(V，E)，当小立方体i和小立方体j中心间距小于D=O((log L)1／3)时，就在顶点i和j之间连接一条边。将从i到j移动的传感器数目记为xij，则移动策略问题可以表示为：
   
    式中：cij表示移动花费，简单情况下表示所移动的距离。在这个优化模型里，式(2)表示流守恒条件，即传感器移出小立方体i的数目减去移进小立方体i的数目要小于或等于小立方体i额外的传感器数目，这保证了移动后每个小立方体移动传感器大于小立方体的空缺，即达到所要求的k覆盖。式(3)则表示移出小立方体i的移动传感器数目的总和要小于或等于它所拥有的移动传感器的数目。
    用同样构造图的方法，模型同样适应于不规则形状的网络。

3 分布式算法
    由上文可知，传感器移动策略就是网络最小花费流问题，已对传感器的最大移动距离有了限制，所以，可以通过更简单的最大流问题找到可行的移动策略来填补每个小立方体的空缺，而不考虑最小花费的问题。关于网络最大流问题有许多有效的算法，本文采取pushrelahcl分布式算法。
    为保持网络的连通性，假设传感器的通信半径大于传感器半径r的2倍。在算法执行前，假设每个静止或移动传感器知道它的位置和位于哪个小立方体里。随机部署岳，考虑传输信息消牦能量的影响，每个单元周期性地选择一个传感器作为代表，收集算法执行前需要的信息，信息形式如下：
   
    其中：ID代表传感器的标志；cube表明传感器在哪个小立方体里；x，y，z表示传感器位于哪个位置信息，代表元会负责与图G中的邻居互传信息。因为随机部署会产生某些单元没有任何传感器，为保持网络的连通性，在算法执行前将距离最近的传感器移动到空单元。
    Push-relabel算法的基本思想是循环地选择多余的流推进到高度比它低的邻居，若没有则重新标记高度，一直到所有的节点没有多余的流。在算法中，把移动传感器从比k个传感器多的小立方体中推向比k要小的小立方体中，并按如下方法来处理图G(V，E)，将其转换为有向图：
    将每个节点j∈V分裂成两个节点iin和iout，并增加一条单向边(iin，iout)，其移动花费为0，且容量约束为mi；iout是每一轮中的源节点，其出边与邻居节点j以单向边(iout，jin)相连，移动花费为cij，容量约束为无穷大，如图1所示。

    移动算法步骤如下：
    (1)对每个小立方体i进行分布式移动算法；
    (2)收集每个小立方体的信息vi和mi；
    (3)令h(iin)=0，h(iout)=0：e(iin)=0，e(iout)=mi-vi，其中h和e分别表示节点的高度和节点中额外的传感器；
   
    (5)根据弧(iout，jin)上的流将传感器移动到小立方体j。
    其中，push-relabel(v)算法步骤为：

    在算法中，节点只需要知道相距为D的邻居节点信息(比如高度)，以此来执行push-relabel算法。算法分为两个步骤，在第一步中，节点将多余的流推入相邻的邻居节点，如果需要重标记，则在第二步中，节点重新标记自己，并通知相邻的邻居节点。在同一个小立方体i中iin和iout之间的推进跟不同小立方体之间的推进除了没有信息传送，其他都是一样的。要注意的是推进和重标记过程只是发送信息，传感器是没有移动的，只有在算法结束后，传感器才根据弧上的流进行移动。
    因为网络图含有O(2L)个节点，每个节点iout至多有O(D3)=O(logL)条出度弧，而每个iin只有一条出度弧(iin，iout)，因此图至多有O(Llog L+L)条弧。根据Goldberg A给出的同步分布式push-relabel算法，时间复杂度为O(|V|2)(V为节点个数)，至多有O(|V|2ε)(ε为弧的数量)的信息交换量，又因为iin和iout之间没有信息交换，所以算法的时间复杂度为O(4L2)，信息交换量为O(L3log L)。

4 仿真与分析
    为了检验理论的正确性，对移动传感器网络k-覆盖仿真。将网络划分为边长(r为传感器半径，k为覆盖因子)的小立方体，将M=ΛL个移动传感器均匀于网络中，其中Λ=O(k)。(具体的M值根据网络中立方体的空缺总额来选定，只要超过空缺总额即可)。仿真结果如图2所示。

    图2表示对固定的k值(k=3)，随着移动距离的变化，不同规模网络存在k覆盖的概率(其中距离被dh规范化)。
    由图2可知，网络从8×8×8增长到20×20×20的小立方体时，网络达到k-覆盖传感器需移动的最大距离都为3dh。这说明，随着网络规模的增大，传感器移动的最大距离增长微小。
    在传感器网络仿真中，其算法性能如图3所示。

    图3表示当k=10，D=4时，随着网络规模的增大，push-relabled算法的性能。
    在上文中，分析了push-relabel算法的时间复杂度为O(4L2)。但从实验结果(如图3(a)所示)可以看出，算法的平均和最大时间复杂度与L呈线性关系，如当网络大小为8 000时，平均只需要1 000轮便可得到解。
从图3(b)曲线来看，网络中所有节点发送信息量的总和随着网络规模的增大呈O(L2+α)(0<α<1)增长，比上文分析的总的信息交换量O(L3log L)要好。由此可知，通过对算法的改进，算法在实际运行中总的性能比push-relabel算法要好一些。

5 结语
    本文在前人研究的基础上给出了三维空间移动传感器最大移动距离的一个界，并采用最大网络流算法，实现了传感器移动策略，减少了每个传感器因移动消耗的能量，提高了网络的覆盖性能。但对于三维网络达到k-覆盖时传感器的具体定位还有待于进一步研究。