基于阿基米德螺线的双汇聚节点重定位策略*

杨 心,冯 勇,黄 祺,郭 龙,吴 渊

(昆明理工大学云南省计算机技术应用重点实验室,昆明 650500)

传感器节点和移动汇聚节点组成的传感器网络WSN(Wireless Sensor Network)为众多应用提供了多样化的服务,如抢险救灾、医疗卫生和环境监测等[1]。在这些应用中,大量传感器随机部署在监测区域,然后通过自组织方式构成网络。

由于WSN中传感器所携带的电池能量十分有限,如何高效利用有限的能量是当前无线传感器研究的一个重要方向。许多学者对WSN的能耗问题进行了研究。例如文献[2-3]都提出了一种节能路由算法来均衡网络中能耗从而延长网络寿命;文献[4]通过调整传感器的位置来避免能量空洞问题,虽然延长了网络寿命,但传感器节点的移动也将消耗能量。因此在目前研究中通常使用汇聚节点来代替传感器节点进行重定位,如文献[5]利用剩余能量信息来动态改变节点的传输半径和汇聚节点移动方案。王章权等人[6]提出了路径选择算法(MPSA),即根据节点的位置和剩余能量信息找到一条较优的汇聚节点移动路径。

汇聚节点一般分为静态汇聚节点和移动汇聚节点。如果汇聚节点始终保持静止将会导致严重的热点问题和能量空洞[7],这是因为越接近汇聚节点,传感器节点就会被越多的传输路径所共享[8]。所以本文讨论的是移动汇聚节点,它具有以下优点[9]:①能实现网络的能量均衡,避免热点问题;②能连接稀疏网络和断裂网络,提高网络覆盖率。在网络中部署多汇聚节点能在很大程度上减少节点的平均跳数,从而有效减少多跳传输的能耗,降低数据传输时延。阿基米德螺线基本上能覆盖整个网络且其具有恒定的线速度和角速度等优点,使得汇聚节点的运动变得可控,而且汇聚节点能直接与网络中大多数节点进行数据传输。故本文采用多个汇聚节点沿着阿基米德螺线运动的方法来减少节点能耗,最大程度的延长网络寿命,文中仿真实验证明其有很好的性能。

1 相关工作

Gu Y等人[10]将汇聚节点的移动模型分为:不可控移动模型(随机移动UMM)和可控移动模型(无约束移动URM和路径约束移动PRM)。在PRM中,汇聚节点沿着固定的轨迹移动,其运动模型简单同时能有效提高系统通信负载和能量效应等性能[11]。故本文采用路径约束模型(PRM)即汇聚节点沿着固定轨迹匀速移动。

目前许多学者对汇聚节点沿着固定轨迹重定位进行了一些研究,如Wang等人[12]提出汇聚节点沿着固定的圆形轨迹移动,通过MECA和FEGASIS两种路由算法将网络分成不同的簇,选择离汇聚节点最近的簇头作为负责数据传送的领导节点。Tunca 等人[13]提出了一种分布式高效节能的环形路由协议,首先环节点通过地理位置路由算法形成环,然后汇聚节点在环上移动并接收锚节点传送来的数据。Na等人[14]则提出了一种移动汇聚节点路由算法(CRA),在该算法中汇聚节点沿着圆行轨迹移动,缓冲区中的节点作为骨干节点来连接节点并进行数据传输,但是作者并没有提出一个最优的聚类算法来确定缓冲区的位置。中南大学的Weng Yanbin[15]提出使用阿基米德螺线的可控汇聚节点移动策略,作者指出阿基米德螺线具有恒定的线速度和角速度,当汇聚节点沿着该螺线运动时,轨迹易被控制。

在网络中部署多个汇聚节点可以有效减少节点在多跳转发数据包上消耗的能量,因为节点将会选择离它最近的汇聚节点进行通信从而在很大程度上减少了平均跳数,降低了数据传输时延。例如文献[16]计算出了多汇聚节点重定位的最优位置,以达到汇聚节点的覆盖度最大化和平均跳数最小化。Chatterjee 等人[17]提出了一种遵循图论方法的多汇聚节点部署技术,以实现最大化网络寿命的同时减少汇聚节点的开销。文献[18]提出多汇聚节点以一个连续近似和协作方法移动到最佳位置,但其在实际部署中经济开销过大且没有考虑多汇聚节点的数据融合问题。Mirela Marta等人[19]指出当传感器节点随机部署时,可通过汇聚节点沿预定轨迹运动得到最优结果,并且多汇聚节点可以有效提高网络寿命。

本文就上述问题提出了一种基于阿基米德螺线的多汇聚节点重定位策略ATSR(Archimedean spiral based Two-Sink Relocation)。该策略采用了多汇聚节点(如双汇聚节点)同时沿着对称的两条阿基米德螺线运动的方式来提升网络寿命。同时对其进行了优化,使本策略的性能得到了进一步的提升。

图1 网络模型

2 网络模型

在构建网络模型(如图1所示)前,需要制定以下假设条件:①n个无线传感器节点以随机部署的方式静态(即静止)分布在区域环境中。②传感区域是半径为R的圆形,所有的传感器节点的传输半径均为rs,且均有一个不同的ID。③传感器节点具有等量且有限的电池电量,汇聚节点移动能力不受限制,能量视为有限,每当它们沿着阿基米德螺线运动完一个循环回到初始位置时,都要去网络中心的基站补充能量。④本文使用与文献[20]相同的无线通信能量模型。在该能量模型中,发送和接收消息是主要能耗。当a传感器节点发送k位的数据给另一个距离它d远的节点b时,可用式(1)计算能耗,b接收此消息所消耗的能量可用式(2)计算:

Es(k,d)=Eelec·k+εamp·k·dm

(1)

Er(k,d)=Eelec·k

(2)

在本文提出的多汇聚节点重定位策略中,采用了阿基米德螺线作为汇聚节点的预设移动轨迹。阿基米德螺线又被称为等速落线,当一个点在阿基米德螺线上运动时,其具有恒定的线速度v和角速度w,r为极径。用rstart代表螺线的初始移动极径。由阿基米德螺线的极坐标方程可得:

(3)

那么一旦确定螺线的起始位置,则可以通过式(3)等比例得出角速度和线速度。由于每条阿基米德螺线都具有一条对称螺线,其极坐标公式中,二者的θ互为相反数,即一条θ<0,另一条θ>0。若将其中一条螺线旋转90°或者270°即可得到另外一条螺线。二者在原点处能够平滑的连接,阿基米德螺线最大特点是,螺距即螺线每条臂的距离都是相等的,即2rn,且在笛卡尔坐标系中,当y为0时,x为2rn。

3 ATSR和IATSR

3.1 ATSR

3.1.1 多汇聚节点

根据螺线公式可知,在其他环境参数不变的情况下,多汇聚节点(n个汇聚节点)的螺距是单汇聚节点螺距的n倍,此时多汇聚节点具有较好的性能,因为与单汇聚节点相比,在单位时间内它能接收更多的数据同时减少了数据传输的平均跳数,大大减少了多跳传输的能耗和传输延迟。本论文取n=2,主要研究双汇聚节点的情况。当单汇聚节点的螺距设置为4rs,对应的双汇聚节点则设置为8rs,rs=5,如图2和图3所示。

图中的两种虚线代表两个汇聚节点的运动轨迹。图3为图2所在坐标系中第1象限局部图,图2左图为单汇聚节点在坐标系中的表示,图2右图为双汇聚节点在坐标系中的表示,其中可以很明显的看出左图中单个汇聚节点运行的轨迹长度要远大于右图中一个汇聚节点运行的轨迹长度,因此双汇聚节点一次循环的周期远小于单汇聚节点。在实际应用时,如果能够保持一个较短的循环周期,也就意味着成本的降低。为了最大化网络环境的覆盖,本论文在提出的策略中使用了两个汇聚节点。

图2 螺距对比整体图

图3 螺距对比局部图

3.1.2 汇聚节点重定位

初始时汇聚节点SA和SB位于螺线的中心,且两条螺线相互对称,随后SA和SB分别以恒定的线速度沿着螺旋轨迹移动。网络中部署的双汇聚节点的运动是对称的,即当汇聚节点SA的坐标为(XA,YA),汇聚节点SB的坐标为(XB,YB)时,XA=-XB,YA=-YB。当汇聚节点到达区域边缘时会立即沿直线返回初始出发点,进行下一次运动。通过这种方法,汇聚节点在传输和接收信息时能节省大量能量。图4通过伪代码显示了具体实现细节。

图4 ATSR的伪代码

3.1.3 收集数据

当汇聚节点沿着阿基米德螺线轨迹移动时,会收集两跳以内的邻居节点的数据信息。假定每次的数据传输成功率均为100%,即节点会在极短的时间内将数据信息传输给汇聚节点,无延时无丢包。本文假设传感器节点和汇聚节点的传输半径均为R,整个网络中数据消息的传输采取最少跳数路由,即传感器节点选取到汇聚节点跳数最少的路径来传输数据。如图5所示,由于本文中汇聚节点可以收集两跳内的数据信息,以其为圆心,汇聚节点最大可以收集半径3R范围内的数据信息,最小可以收集半径R范围内的数据信息。当汇聚节点在自身轨迹上运动时,会间隔R个单位长度收集一次数据,来确保数据的收集。

图5 汇聚节点传输半径示意图

当WSN工作时,传感器每隔固定单位时间收集数据信息。当汇聚节点沿着阿基米德螺线运动进入节点的传输半径时,轨迹周边一跳或者两跳邻居节点将把收集的数据信息传输给汇聚节点。而离汇聚节点nR远的节点将以多跳方式把数据传送给邻居节点直至传送给汇聚节点,如图6所示。

图6 数据的收集

3.2 IATSR

数据收集间隔是汇聚节点每次移动的判断,如果汇聚节点移动的直线距离大于给定阈值则向周边节点发送一个请求信息并开始收集数据,反之则不。在ATSR中,当收集间隔过小时,会导致某些节点重复收到汇聚节点的数据请求信息,带来额外的能量消耗。

如图7所示,假定T时刻,汇聚节点在位置PositionA向周边节点p发送一个请求数据包。节点q在p的传输半径内,而不在汇聚节点的传输半径内,节点p必然向q发送一个信息,告知其汇聚节点需要收集数据。假定节点q已存储一定量数据,这时节点q必然会反向沿着请求消息路径,向汇聚节点传输数据。而在T+1时刻汇聚节点运动到PositionB,PositionA和PositionB的直线距离小于传输半径R。由于节点p仍在汇聚节点的传输半径内,则会重复发送消息,对节点p和节点q的电池电量造成了不必要的损耗。由能耗模型可知,节点p额外接收和发送一次消息,节点q额外接收一次消息。最小额外能耗Emin为节点p的一次接收能耗:

ESink→p(k)=Eelec*k

(4)

图7 额外能耗示意图

最大额外能耗Emax为两次接受和一次发送能耗:

Emax=ESink→p(k,dSink→p)+Ep→q(k,dp→q)+Ep→q(k)

(5)

式中:

(6)

即:

(7)

如果节省这部分能耗,将会极大的提高网络寿命,比如通过调整汇聚节点在螺线上的收集间隔来避免额外能耗。正如前面所讨论的,当数据收集间隔过小时,将导致一些节点频繁的接收汇聚节点的数据请求消息,从而带来额外的能量消耗。相反当收集间隔过大时不利于汇聚节点与邻居节点的通信和数据传输。因此在仿真实验中,本论文针对IATSR的收集间隔进行了测试,测试结果见下一节。

4 仿真实验

前一节详细介绍了基于阿基米德螺线的多汇聚节点重定位策略及其改进策略,本节对两种策略的性能进行了实验验证。汇聚节点的初始位置分别为(R,0)、(-R,0),汇聚节点的角速度也与传感器半径的大小有关,二者成反比。最终实验目的是为了提高网络生存寿命,故实验结果均以网络寿命为对比,其中网络寿命被定义为从网络初始时刻开始到网络中第1个节点能量耗尽退出网络为止所经历的时间[21]。在实验中,每隔一段时间随机选取某些节点产生等大的数据包,默认实验参数设置如表1所示。

表1 默认实验参数

4.1 实验结果

对于IATSR和ATSR的区别,上文已详细阐述。数据消息的收集间隔以传感器传输半径R作为基准,即nR,通过实验得到n的大小。实验中,节点数量设为1 200个,其他参数参考表1。得到的数据如图8所示。

可以看出,n为1时网络寿命最低。当n从1变化到1.6时,网络寿命呈上升趋势,急剧增加。而n从1.6变化到4时,大体保持平衡,但在n为3.2时,有一个较大的下降变化。考虑到本实验中,传感器节点均采取随机部署,对网络寿命的性能会有一定的影响,当n等于2时,基本处于中间水平,所以本文中取n为2。

图8 参数n从1变化到4时对网络寿命的影响

在本文中,假设数据以每个信息10 s的平均速度产生成数据包,数据传输延迟被定义为信息从产生到传送给汇聚节点的时间间隔。如图9所示,可以看出汇聚节点数量从0增加到6时,传输延迟减少了近10倍(从1 130 s～153 s),两个汇聚节点的传输延迟也要远远小于单个汇聚节点。这是因为在相同的环境中,多汇聚节点的传输延迟小于单个汇聚节点,即多汇聚节点在单位时间内能收集和传送更多的数据。

图9 多汇聚节点的传输延迟

图10 节点能量从1 J变化到5 J时的网络寿命的变化

从图10中可以看出,当单个节点初始总能量从1 J变化到5 J时,任何一种重定位策略也都会增加,并且基本为一条直线,起伏不大。IATSR和One-Sink相比,网络寿命分别提升了88.56%、72.96%、72.42%、71.46%和73.22%,性能提升了大约70%到80%。和Two-Sink相比,网络寿命分别提升了57.09%、46.23%、48.67%、52.74%和52.84%,性能提升了大约45%到60%。实验数据较为规律,这是必然的。节点能量的增加使得单个节点可持续运作的时间也增加了。IATSR的改进,使得能耗得以进一步降低,提高了网络寿命。

当传感器节点数目从1 200个改变到2 000个时,所有的策略都呈下降趋势,但IATSR依然比其他策略的性能要好,如图11所示。和One-Sink相比,网络寿命分别提升了68.08%、78.44%、76.78%、81.71%和81.30%,性能提升了大约70%到80%。和ATSR相比,网络寿命分别提升了54.88%、57.97%、61.30%、53.10%和58.96%,性能提升了大约50%到60%。出现该结果的原因可能是没有对路由进行优化,只是简单的使用了最少条数路由。使用最少跳数必然会有重复接收消息的节点,这是无法避免的。节点数目的增多,意味着单位面积内的节点密度也会增加。那么会有更多的数据节点出现在汇聚节点两次收集间隔的重复区域。这必然会带来更多的能量消耗,导致节点数目越多网络寿命反而下降的情况。

图11 节点数目从1 200个变化到2 000个时的网络寿命的变化

图12 汇聚节点速度从1 m/s～5 m/s时网络寿命的变化

图12所示的改变汇聚节点速度时网络寿命的变化。IATSR和One-Sink相比,网络寿命分别提升了76.10%、24.96%、46.12%、61.02%和49.21%,性能提升了大约25%到75%。和ATSR相比,网络寿命分别提升了51.16%、25.23%、52.05%、70.81%和67.86%,性能提升了大约50%到70%。图中,汇聚节点线速度小于2 m/s时,网络寿命会保持一定水平,当增加到3 m/s时,会有小幅度提升。而一旦线速度继续增加时,网络寿命就会呈现下降趋势,且ATSR在线速度超过2 m/s时,网络寿命就一直比One-Sink还要低。这是因为汇聚节点的移动速度即为螺线的线速度,在保持螺距不变的情况下,移动速度增大(减小),角速度也会增大(减小)。那么在单位时间内,汇聚节点每次移动的间隔同样会增大(减小),而数据收集间隔是汇聚节点每次移动的判断,如果其大于阈值则不收集,反之则不,并且线速度越大,所形成的螺线轨迹越不光滑,变得如蜘蛛网一样,所以说汇聚节点的移动速度会在一定程度上影响到网络寿命。

由于上文提到,传感器节点的传输半径和角速度大小成反比。为了方便计算,以及能让网络中部署双汇聚节点时,能和One-Sink做对比,传输半径选择了4种变化,分别是5 m、10 m、20 m和40 m,那么对应的角速度分别设置为0.157 rad/s、0.078 5 rad/s、0.039 25 rad/s、0.019 625 rad/s,结果如图13所示。和One-Sink相比,网络寿命分别提升了58.38%、82.69%、103.23%和141.64%,性能提升了大约60%～140%。和Two-Sink相比,网络寿命分别提升了44.57%、56.19%、85.49%和96.85%,性能提升了大约45%到95%。虽然3种策略整体呈下降趋势,但IATSR仍然比One-Sink和ATSR要好。从得到的仿真实验性能提升比可以看出,随着传输半径的增加,性能提升比显著上升了。随着传输半径的增加,汇聚节点传输半径内可以接受到的节点数目也在增加。由于本仿真实验采用的是最少路径路由,最多为两跳,由能耗公式可知,半径越大其能耗会急剧增加,从而导致网络寿命的下降。

图13 节点传输半径分别为5 m、10 m、20 m和40 m时网络寿命的变化

5 总结

汇聚节点重定位是一种能有效延长网络寿命的方法,它避免了汇聚节点在一个地方停留太久而过度损耗邻近节点的能量。当传感器节点以随机的方式均匀分布时,汇聚节点沿着预设轨道可以获得最优效果,并且多汇聚节点能够有效提升网络寿命。本文提出了一种多汇聚节点重定位策略(ATSR),它在阿基米德螺线的基础上使用了两个汇聚节点。同时本文对该策略进行了改进并提出了一个性能更好的策略(IATSR),它通过改变汇聚节点在螺线上数据收集间隔的大小节省了更多的能耗,仿真结果表明在延长网络寿命方面本文两个策略优于对比策略。

[1] Chirihane G,Zibouda A,Mohamed B. An Adaptive Clustering Approach to Dynamic Load Balancing and Energy Efficienct in Wireless Sensor Networks[J]. Energy,2016,114(1):647-662.

[2] 刘半藤,周莹,陈友荣. 基于加权路由思想的无线自组织网络生存时间优化算法研究[J]. 传感技术学报,2017,30(3):463-466.

[3] 孙彦景,林昌林,江海峰. 一种能量高效的分布式非均匀分簇路由算法[J]. 传感器技术学报,2015,28(8):1194-1200.

[4] Wu J,Yang S. SMART:A Scan-Based Movement-Assisted Sensor Deployment Method in Wireless Sensor Networks[C]//Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE,2005,4:2313-2324.

[5] Wang C F,Shih J D,Pan B H,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.

[6] 王章权,陈友荣,任条娟,等. 数据传输时延和跳数受限的Sink节点移动路径选择算法[J]. 传感器技术学报,2016,29(4):583-592.

[7] Zhang P,Xiao G,Tan H P. Clustering Algorithms for Maximizing the Lifetime of Wireless Sensor Networks with Energy-Harvesting Sensors[J]. Computer Networks,2013,57(14):2689-2704.

[8] Zhu C,Wu S,Han G,et al. A Tree-Cluster-Based Data-Gathering Algorithm for Industrial WSNs with a Mobile Sink[J]. IEEE Access,2015,3:381-396.

[9] Kinalis A,Nikoletseas S,Patroumpa D,et al. Biased Sink Mobility with Adaptive Stop Times for Low Latency Data Collection in Sensor Networks[J]. Information Fusion,2014,15:56-63.

[10] Gu Y,Ren F,Ji Y,et al. The Evolution of Sink Mobility Management in Wireless Sensor Networks:A Survey[J]. IEEE Communications Surveys and Tutorials,2016,18(1):507-524.

[11] Khan A W,Abdullah A H,Anisi M H,et al. A Comprehensive Study of Data Collection Schemes Using Mobile Sinks in Wireless Sensor Networks[J]. Sensors,2014,14(2):2510-2548.

[12] Wang J,Cao J,Cao Y,et al. An Improved Energy-Efficient Clustering Algorithm Based on MECA and PEGASIS for WSNs[C]//2015 Third International Conference on Advanced Cloud and Big Data,IEEE,2015:262-266.

[13] Tunca C,Isik S,Donmez M Y,et al. Ring Routing:An energy-Efficient Routing Protocol for Wireless Sensor Networks with a Mobile Sink[J]. IEEE Transactions on Mobile Computing,2015,14(9):1947-1960.

[14] Na W,Xiao-gang Q,Li D,et al. Clustering-Based Routing Algorithm in Wireless Sensor Networks with Mobile Sink[J]. Journal of Networks,2014,9(9):2376-2384.

[15] Weng Y,Jia W,Wang G. Joint Routing and Controlled Mobility for Energy Efficiency in Wireless Sensor Networks[C]//2010 3rd International Conference on Advanced Computer Theory and Engineering(ICACTE). IEEE,2010,4:V4-423-V4-427.

[16] Dandekar D R,Deshmukh P R. Energy Balancing Multiple Sink Optimal Deployment in Multi-Hop Wireless Sensor Networks[C]//Advance Computing Conference(IACC),2013 IEEE 3rd International.

[17] Chatterjee P,Das N. Multiple Sink Deployment in Multi-Hop Wireless Sensor Networks to Enhance Lifetime[C]//Applications and Innovations in Mobile Computing(AIMoC),2015. IEEE,2015:48-54.

[18] Yuan T,Xu J,Zhang J. Energy Efficient Multi-Sink Relocation in Wireless Sensor Networks[J]. Jisuanji Gong Cheng Yu Yingyong(Computer Engineering and Applications),2013,49(2):19-23.

[19] Yang Y,Fonoage M I,Cardei M. Improving Network Lifetime with Mobile Wireless Sensor Networks[J]. Computer Communications,2010,33(4):409-419.

[20] Wang C F,Shih J D,Pan B H,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.

[21] Miguel S,Javier G,Baldomero C P. Multipath QoS-Driven Routing Protocol for Industrial Wireless Networks[J]. Journal of Network and Computer Applications,2016,74:121-132. IEEE,2013:408-412.