基于蜂巢状虚拟结构的单汇聚节点节能重定位策略*

黄　祺， 冯　勇， 李修琪， 黄北北

(昆明理工大学 计算机重点实验室，云南 昆明 650504)



基于蜂巢状虚拟结构的单汇聚节点节能重定位策略*

黄祺， 冯勇， 李修琪， 黄北北

(昆明理工大学 计算机重点实验室，云南 昆明 650504)

摘要:提出了一种基于蜂巢状虚拟结构的单汇聚节点节能重定位(HEESR)策略。此策略中整个网络覆盖区域被划分成多个蜂巢状虚拟网格结构。汇聚节点周期性地收集周边虚拟蜂巢网格的平均剩余能量和网格内单个节点的剩余能量，基于这些信息汇聚节点进行重定位。为进一步提高能量效率，HEESR策略还采用基于剩余能量水平的通信半径调整机制。仿真实验表明：与现有几种汇聚节点重定位方法相比，HEESR能够更有效地降低能量消耗、延长网络寿命。

关键词:无线传感器网络； 汇聚节点重定位； 蜂巢虚拟网格； 网络寿命

0引言

通常无线传感器所能携带的电池能量会十分有限，如何高效利用有限的能量是当前无线传感器网络(WSNs)研究的一个重要领域。在当前研究阶段，通常考虑使用汇聚节点来集中处理感知到的数据信息。但如果汇聚节点始终保持静止，随着时间的推移，不均衡的能耗将会导致严重的热点问题和能量空洞[1～3]。引起这一现象的原因在于越接近汇聚节点，就会被越多的传输路径所共享。目前研究中，运用虚拟分层的方法可以将无线传感器网络划分成两个或更多的网络层，分层方法[4]可以分为5种类型，分别是簇、网格、多叉树、骨干网和指定区域。

基于网格的方法是将网络划分成多层次网格的虚拟层次结构[5]。选择固定的节点或者具体坐标来构成交叉区域的网格。由于网格是一个几何结构，并且每个传感器节点的地理坐标都需要被知晓，因此，地理位置感知传感器是基于网格方法的首选。

基于簇的方法使用了分簇机制将网络分层，并在每层或者每个网格中使用簇头作为高层次收集转发节点[6]。每个簇头加入一个且只能加入一个最近的簇，并感知收集其所在簇中的数据。相比于网格来说，成簇要更加复杂困难。然而，由于簇是参照节点拓扑感知信息建立的，虚拟层次结构实现也尤为有效。

基于树的方法将汇聚节点作为整个传输网络的根节点，普通无线传感器节点则是叶节点[7]。除叶节点外，其余节点均为高层次节点。和基于网格类似，这些节点同时也是源节点。

基于骨干网的方法中源节点通过骨干网来向汇聚节点传输感知信息[8]。骨干网由网关节点和簇节点组成。骨干网较为适用于延迟容忍网络，因为只有当汇聚节点靠近所选择的网关时会传输聚合数据。

基于指定区域的方法指定在特定区域中的节点作为分层结构中的高层节点，而不是建立复杂的结构[9]。这种层级构造的成本和其他方法构造方法相比是最小的。在避免改变划分结构的基础上，为了减轻热点问题，特定区域的大小必须足够大，以减少对高层次节点负载。

本文提出了一种基于蜂窝网格的汇聚节点重定位(HEESR)策略。实验结果表明：HEESR策略能有效均衡传感器节点的能耗，并延长网络寿命。

1HEESR策略

1.1网格模型

首先，在顶点到几何中心等距(距离为R)的多边形中，能够完整且无重叠覆盖某一区域的形状有正三角形、正方形和正六边形(蜂窝网格)，但是在这三者中，只有正六边形所覆盖的面积最大，其次蜂窝网格具有当圆心处于形心时，所用圆的数量最少的数学特性，最后因为考虑到实际运用中所需设备成本的问题，本方法采用了蜂窝网格。用蜂窝网格来实现无线传感器网络，可以实现低成本高效率的大面积覆盖。当区域给定，有限的资源可以在一定条件下重复利用。当区域内的资源饱和过剩时，可以将蜂窝网格更加细致的划分，从而得到更多的蜂窝网格，进一步提升资源利用率。

图1　网格模型与移动策略Fig 1　Grid model and mobile strategy

1.2HEESR

如图1所示,明显能看出除汇聚节点Sink自身所在的蜂巢网格e，周边有六个网格a,b,d,f,g,h，分别用 (1≤i≤6)表示。这六个蜂巢网格的形心即为Sink下一步移动的候选位置。用H*来记录Sink曾经移动的位置。因为节点随机分布，每个网格中节点数目Si不一致，最低为0。分别给予六个网格一个权值wi，wi代表每个网格的平均剩余能量。将R(n)设为每个网格总剩余能量，则wi=R(n)/Si。每隔一定时间，通过能量感知路由协议MCP[10]，汇聚节点Sink收集Hi的剩余能量信息wi和每个节点的信息。其wmin≤…

图2　HEESR流程图Fig 2　Flowchart of HEESR

依据判断所得权值wmv，Sink选择移动的位置。当数据信息收集处理完毕，汇聚节点Sink就会以一个恒定的速度向选择的网格中心移动。当Sink到达预定位置，整个网络中的拓扑就会依据Sink的当前位置产生变化。Sink会在当前位置停留一定时间来实时地收集数据信息。依据网络中能量变化，汇聚节点Sink重定位的过程会一直持续下去，直至网络中第一个节点死亡。

图3显示了Sink移动后网络路由路径变化，其中,每个圆代表一个网格。可以看出当Sink从H1移动到H2时，只有一条路径的方向发生了改变。

图3　Sink重定位后路由路径的变化Fig 3　Routing path change after sink relocation

1.3传输半径调整机制

2性能分析

2.1能耗模型

本文中所用的无线通信能量模型与文献[11,12]相同。该无线通信模型给出了一个阈值d(d是常数，数值取决于使用环境)。根据发射和接收节点之间的距离，传感器节点可以分别计算发送和传输数据时所需要的能量。当传感器节点p向距离d外的另一个节点q发送k字节的数据时，它可以用下面的式(1)来计算能耗

Es(k,d)=Eelec·k+Eamp·k·dn.

(1)

当节点q接收p发送的消息时，则用式(2)来计算能耗

Er(k,d)=Eelec·k,

(2)

在上述公式中Eelec为由所述传感器节点收发电路时所消耗的能量。Eamp为由放大器所消耗的能量。因为所有传感器节点位置保持不变，所以,节点p向节点q传输k字节产生的能耗与节点q向节点p传输k字节产生的能耗相等。

2.2参数设置

本文中，所有普通传感器节点都以静止的方式随机部署在仿真环境中汇聚节点是唯一具有移动能力的特殊节点。当网络中第一个节点死亡时，网络被认为是已死亡。

表1　默认实验参数

图4　节点数目对网络寿命的影响Fig 4　Effect of number of nodes on network lifetime

图5　节点初始能量对网络寿命的影响Fig 5　Effect of initial energy on network lifetime

图6　传输半径对网络寿命影响Fig 6　Effect of transmission radius on network lifetime

图7　仿真环境大小对网络寿命的影响Fig 7　Effect of size of simulation area on network lifetime

3结论

本文提出了HEESR策略,基于邻居网格中节点的剩余能耗和网格的平均剩余能量，汇聚节点可以向周边六个网格进行移动。仿真实验表明：HEESR策略能够有效降低传感器节点的传输负载和能耗，达到更长的网络寿命。在接下来的研究中，会考虑当节点平均能量下降到预定阈值时，调整网络虚拟网格大小和采用多汇聚节点数目时的汇聚节点重定位策略。

参考文献:

[1]吴晓培,吴跃,陈湘.密集传感器网络中节点随机调度算法研究[J].电子科技大学学报,2010,39(1):119-122.

[2]马玉芳,陈建华,郝杨满.基于汇聚节点移动的能量均衡路由协议的研究[J].计算机工程与应用,2013,49(14):77-80.

[3]吴小兵,陈贵海.无线传感器网络中节点非均匀分布的能量空洞问题[J].计算机学报，2008(2):253-261.

[4]Tunca Can,Sinan Isik,Donmez M Yunus,et al.Distributed mobile sink routing for wireless sensor networks:A survey[J].IEEE Communications Surveys & Tutorials,2014,16:877-897.

[5]Luo H,Ye F,Chen J,et al.TTDD:Two-tier data dissemination in large-scale wireless sensor networks[J].Wireless Networks,2005,11(1/2):161-175.

[6]Yuan.Xunxin,Zhang Ruihua.An energy-efficient mobile sink routing algorithm for wireless sensor networks[C]∥Proc of Wireless Communications Conf Networking and Mobile Computing,Wuhan,2011:1-4.

[7]Kim H S,Abdelzaher T F,Kwon W H.Minimum-energy asynchronous dissemination to mobile sinks in wireless sensor networks[C]∥Int’l Conf on Embedded Networked Sensor Systems,SenSys,03,New York,2003:193-204.

[8] Lu J L,Valois F.On the data dissemination in WSNs[C]∥Conf on Wireless Communications,Networking and Mobile Computing,New York,2007:58.

[9] Tunca C,Donmez M Y,Isik S,et al.Ring routing:An energy-efficient routing protocol for wireless sensor networks with a mobile sink[C]∥2012 4th Int’l Conf on Signal Processing and Communications Applications,Fethiye,Mugla,Turkey:2012:1-4.

[10] Wang Chufu ,Shih Jauder ,Pan Bohan,et al. A network lifetime enhancement method for sink relocation and its analysis in wireless sensor networks[J].IEEE Sensors Journal,2014,14(6):1932-1943.

[11] 刘明,龚海刚,毛莺池,等.高效节能的传感器网络数据收集和聚合协议[J].软件学报，2005,16(12):2106-2116.

[12] Sun Yi,Wei Huangfu,Sun Limin,et al.Moving schemes for mobile sinks in wireless sensor networks[C]∥International Perfor-mance Computing and Communications Conference,New Orleans,Louisiana,2007:101-108.

A strategy for energy-efficient relocation of single sink node based on honeycomb virtual structure*

HUANG Qi, FENG Yong, LI Xiu-qi, HUANG Bei-bei

(Yunnan Key Laboratory of Computer Technology Application,Kunming University of Science and Technology,Kunming 650504,China)

Abstract:Propose a strategy for virtual honeycomb-based structured energy-efficient single sink node relocation (HEESR).In this method,overall network coverage field is divided into several honeycomb virtual grid structure Sink node periodicly collect average residual energy of surrounding grids and residual energy of single node within grids and sink node is relocated based on these information.In order to increase energy efficiency,a radius adjustment strategy is used.Simulation shows that HEESR can significantly reduce energy consumption,improve network lifetime,compared with other methods of sink node relocation.

Key words:wireless sensor networks(WSNs); sink node relocation; honeycomb virtual grid; network lifetime

DOI:10.13873/J.1000—9787(2016)03—0133—04

收稿日期：2015—06—25

*基金项目：国家自然科学基金资助项目(61262081)

中图分类号:TP 212

文献标识码:A

文章编号:1000—9787(2016)03—0133—04

作者简介:

黄祺(1990-)，男，安徽马鞍山人，硕士研究生，主要从事无线传感器网汇聚节点移动策略的研究。