基于移动无线传感器网络的k-阶覆盖算法

徐晋辉

(淮北职业技术学院 基础部，安徽 淮北 235000)

基于移动无线传感器网络的k-阶覆盖算法

徐晋辉

(淮北职业技术学院 基础部，安徽 淮北 235000)

在移动无线传感器网络中，传感器节点可能由于自身移动、能量损失、物理损坏、错误和故障等因素的影响，从而出现覆盖漏洞的情况，继而导致网络覆盖效率低下。本文就此设计了一个新的移动无线传感器网络覆盖算法，基于分簇的方式，而且能够实时监测网络中出现的覆盖漏洞，并迅速进行修复。仿真结果表明，对于移动无线传感器网络，该算法不仅能够实现所期望的覆盖均匀度，还能够增加覆盖面积，提高网络覆盖率，而且性能要优于VFA。

无线传感器网络；移动；网络覆盖；分簇；VFA

1 引言

无线传感器网络是伴随无线通信和嵌入式计算技术、传感器技术、微机电技术、分布式信息处理技术的进步而发展起来的一种新兴的信息获取技术，是目前国际上备受关注的、多学科高度交叉、知识高度集成的前沿热点研究领域[1]。无线传感器网络中的每个节点都含有一个多功能传感器，它们不仅体积小、价格便宜、低能耗、支持短距离通信，而且还具备信息采集、数据处理、数据传输、相互通信的功能。因此，无线传感器网络能够通过各类集成化的微型传感器协作地实时监测、感知和采集目标环境或监测对象的信息，然后通过自组多跳的无线传播方式传送给用户终端，从而实现物理世界、计算世界以及人类社会三元世界的连通。

随着无线传感器网络在技术与应用方面的惊人发展，其中的一点就是得到了移动领域方面的快速关注。可将传感器网络的移动性分成两类：内部移动性和外部移动性[2]。内部移动性指的是：在传感器网络范围内，传感器自己能够从一个位置移动到另一个位置。该分类的一个典型实例：将传感器安置在一个移动平台上(机器人)，它能够自行决定来作出移动，从而完成一些特定的任务目标，比如：修复网络覆盖漏洞，从而达到更好的感应效果。另一方面，外部移动性指的是：特定的外部代理在传感器网络中的移动。该分类的一个典型实例：一种交通工具或者一个士兵，为了收集数据、补充传感器能量、以及节点定位等目的，在传感器网络中的移动。

当网络中的一些传感器由于故障，能量损失等原因而失效时，就会产生网络覆盖漏洞，进一步影响网络连通性。此时，就可以通过移动传感器来修复，从而提高网络覆盖率，增加网络覆盖面积，实现均匀覆盖，增强网络连通性等目的。移动传感器还能够通过移动到事件发生的附近，得到更好的感应，从而加强事件的检查质量和可靠性。相对于静态传感器节点，移动传感器节点能够实现更高程度的覆盖和连接[3-5]。本文设计了一个新的移动传感器网络覆盖算法，不仅能够有效地提高网络覆盖率，而且还大大增加了网络覆盖面积，可以达到特定的覆盖均匀度，充分利用传感器节点的能量，从而延长网络的使用寿命，提高网络的综合应用性能。

2 算法实现

2.1 定义问题

本文研究的对象是移动无线传感器网络，通过随机部署的方式将传感器节点散播在目标区域范围之内，然后根据具体应用需求，把目标区域划分成若干个小正方形，我们称这样的小正方形为网格。在对整个传感器网络网格化的基础之上，实时监测网络中存在的覆盖漏洞，并迅速进行相应地修复。

假设：移动传感器网络所覆盖的目标区域为一个长方形区域，用A来表示，区域的长为L，宽为R。初始部署时的传感器数目为N，且其ID号为Si，用于唯一标识传感器节点。为了定位好传感器节点，我们用Loc_Si来表示它们的位置，其坐标为(xi，yi)。在本文中，每个传感器都是同构的，而且都能够通过GPS来获取自身当前的位置信息。传感器的感知半径为Rs，连通半径为Rc，生命周期为T，每次移动距离为 F。网格的边长为 Rgrid，且其 ID 号为 Gri，j，网格内对应的传感器数目为Numi，j。期望值为k，用来表示每个网格内希望所部署的传感器数目。

定义1：传感器节点的 ID 为 Si，i<=N，且i∈Z。

定义2：与网格四周相邻的网格，称为此网格的邻居网格。

定义3：当传感器节点从当前网格移向一个邻居网格时，称此次移动为一跳。

定义5：两个传感器节点的欧氏距离为

定义7：本文所提的基站指的就是汇聚节点(Sink节点)。

定义8：如果 Numi，j＝0，则 Gri，j为覆盖漏洞。

2.2 设计原理

本文所提出的算法是运行在基站上，属于集中式的覆盖算法。针对目标区域A，传感器网络中的每个节点，能够通过GPS来决定自身的位置，然后再将位置信息转发给基站。因此，基站就能够通过这样的方式来收集每个网格内的传感器信息，并将这些传感器位置信息存储在基站上。待信息收集完毕之后，基站就会针对整个传感器网络，并将其划分成m×n个网格。同时，在基站上记录每个网格的传感器数目。

当网络全部网格化之后，首先进行横向扫描，实现横向网格内传感器数目的均匀化。接着进行纵向扫描，实现纵向网格内传感器数目的均匀化。通过一次横纵扫描就可以基本实现整个网络的全局覆盖均匀化，再结合网格内传感器的有关信息来决定移动序列(哪个传感器应该移动，移动到哪里)，轮循执行该算法，可以最终实现全局覆盖均匀化。每执行一次该算法，得出移动序列之后，都是通过基站来将移动序列转发给网络中相应的传感器，控制其移动。

在整个网络运行的过程中，基站是能够沿着网络四周的边缘进行移动，并收集传感器节点的相关信息，以减少网络成员节点的能量损耗，从而延长整个网络的使用寿命。算法的运行策略，属于集中式的，通过基站运算得出移动序列，再将指令发送给传感器节点，控制传感器的移动。基站还能够对整个网络进行实时监控，一旦发现网络覆盖漏洞，就会及时修复。

2.3 网格化网络

当移动无线传感器网络初始部署之后，所有的传感器节点就会通过使用自身配置的GPS设备来获取当前的位置，并将其存储在Loc_Si当中，继而将该信息数据包和自身ID号Si一并转发给基站。在基站收到这些信息之后，就会先将这些信息存储起来，然后再将其ID号Si发送给相应的传感器节点，以示确认收到此信息。经过一段时间之后，如果网络中没有位置信息数据包转发了，基站就会广播一次所收到的全部位置信息给相应的传感器节点，当这些节点收到此时的信息数据包后，就会再回复一个自身的ID号Si信息数据包给基站，来确认自身存在于该传感器网络当中。在基站进行信息采集完成之后，就会根据该次收到的ID号Si信息数据包来建立一个数组Loc[N]，用于存储整个网络中传感器节点的位置信息。而且，此数组是以传感器节点的ID号Si来顺序存储对应的位置信息，如公式(1)所示。如果其间有的ID号没有对应的位置信息，就会将其值置0，用来表示网络中不存在该传感器节点。

在位置信息采集并存储完成之后，基站首先会找出最靠近网络边缘的东南西北方向上的四个传感器节点位置，接着找出传感器部署最密集的地方，再根据k的值和网格边长Rgrid来共同决定目标监测区域A的范围。此时，整个传感器网络的网格化已经建成。在基站上会根据传感器的位置来确定它们所在的网格，并建立一个二维数组Grid[i][j]，用于存储网格的 ID 号 Gri，j和网格内的传感器数目 Numi，j，如图1所示。长方形指的就是目标监测区域A，长为L，宽为R。在长方形内的正方形小方格表示的就是网格，其左上角蓝色数字表示的就是网格ID号，如Gr1，1＝1。黑色圆圈表示网格内的传感器，圆圈内的数字表示当前网格内的传感器数目，如Num1，1＝6。第一个网格上边的红色线条表示网格的边长Rgrid。

图1 网格化网络示意图

2.4 决定移动序列

在网络网格化之后，就便于计算出传感器节点的移动序列。利用二维数组Grid[i][j]，可以先计算数组中每行的传感器数目之和，再对每行求均值ki，求出的ki就表示所有横向网格内传感器数目的均值。

当求出每行的均值之后，接着就找出每行中传感器数目最大的列，并以该列为中心，通过移动该列内的传感器节点，来保持以该列为中心的两边传感器数目相等。然后分别对该中心两边的传感器进行递归操作，当该行内传感器的数目都基本接近ki为止，即｜Numi，j-ki｜<=1。在所有横向网格内的传感器都均匀化之后，就进行纵向扫描。纵向扫描的方法和横向扫描的方法基本一样，只是先得求出每列的均值kj，求出的kj就表示所有纵向网格内传感器数目的均值。最后算出的kj，其值就等于期望值k。

通过横纵两次扫描之后，整个传感器网络已经基本实现均匀化了。如果网络中还有覆盖漏洞或者覆盖不均匀的情况存在的话，就可以再运行算法进一步调整网络部署，以实现整个传感器网络最均匀化，也就是均匀度I取最小值的时候。

在传感器网络实现均匀覆盖的同时，总的覆盖面积也增加了不少，覆盖面积S公式如下。

kCA算法伪代码如下所示：

3 仿真

N表示网络中传感器的数目，仿真过程采用了N＝200和N＝100两种方式。实验主要是为了验证传感器网络在初始部署和最终部署时的覆盖面积和覆盖均匀度，也就是利用公式(1)和(2)，在算法执行之后，都有明显增加和提高，如图2所示。实验还仿真了VFA算法[6]，并与文中设计的算法进行了对比。由于本文算法在簇内结合应用了VFA算法，从而实现了局部优化部署，有效地避免了VFA算法中出现的传感器来回往返移动的情况。因此，在总体上节省了不少能量，延长了网络的使用寿命。

图2 kCA与VFA算法的对比

4 总结

通过反复执行mWSNkCA算法，可以使得移动无线传感器网络增加覆盖面积，并达到所期望的覆盖均匀度，不仅能够修复网络中存在的覆盖漏洞，还能够增强网络的连通性，确保数据的有效传输。在算法执行的前期，网络中的传感器部署能够实现局部的均匀覆盖，但最终能够实现全局的均匀覆盖。

[1]Akyildiz I.F.，Su W.,Sankarasubramaniam Y.Wireless Sensor Networks:a Survey[J].Computer Networks.2002，38(4)：393-422.

[2]Sriram Chellappan.On Deployment and Security in Mobile Wireless Sensor Networks:Algorithms Design,Vulnerability Assessment and Analysis[M].ISBN:363918257X.VDM Verlag,July 2009，(19)：11-23.

[3]T.Cormen，C.Leiserson，R.Rivest and C.Stein.Introduction to algorithms[M].in MIT Press，2001.

[4]A.v.Goldberg.An efficient implementation of a scaling minimum-cost flow algorithm[J].J.Algo rithms 1997.22.

[5]A.V.Goldberg and R.Tarjan. Solving minimum-cost flow problems by successive approximation[C]//in Proceedings of ACM Symposium on Theory of Computing (STOC)，(New York)，May 1987.

[6]Yi Zou and Krishnendu Chakrabarty.Sensor Deployment and Target Localization Based on Virtual Forces[C]//IEEE INFOCOM 2003.

Mobile Wireless Sensor Networks Based on K-covering Algorithm

Xu Jin-hui
(Huaibei Vocational&Technical Collgeg，Huaibei Anbui 235000)

In mobile wireless sensor network，considering that sensors node may be in the intersection of no-signal area due to the causes of its move，the energy loss，physical damage，errors，failures and so on，leading to less effect of the network-covering.This paper designed a new algorithm for mobile wireless sensor network coverage，clustering-based approach，can monitoring the network coverage holes in real-time and quickly repaired.Simulation results show that for mobile wireless sensor network，the algorithm can achieve the desired uniformity of coverage，increased coverage，improved network coverage，and its performance is better than VFA.

wireless sensor network；mobile；network coverage；cluster；VFA

TP39

A

1673-2014(2012)02-0064-04

2012—03—18

徐晋辉(1973—)，女，安徽淮北人，实验师，主要从事无线传感器网络研究。

(责任编辑 单麦琴)