三维无线移动传感器网络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的移动传感器数目的总和要小于或等于它所拥有的移动传感器的数目。
用同样构造图的方法，模型同样适应于不规则形状的网络。