基于三维胞元空间的能量高效性多通道协作路由算法

刘俊延 孙 晖柯 涛 路 扬

(浙江大学电气工程学院 杭州 310027)

1 引言

近年来，无线传感器网络(Wireless Sensor Network, WSN)被广泛应用于智能交通、农业监测、军事监控等领域[13]-。路由算法作为WSN应用的重要环节，一直是研究热点之一[4,5]。相比其它的路由算法，基于地理位置信息的 WSN路由无需消耗额外的能量和存储空间建立和维护路由链表，更加符合WSN路由的设计要求[6]。

基于地理位置信息的路由算法中，Fin[7]提出的贪婪(greedy)路由是有效的路由法则，但是贪婪算法会导致遇上局部最小节点后无法继续路由的情况。Choi等人[8]通过鉴定空洞边界有效地避开了局部最小节点，但传递路径迂回且延时较长；文献[9]提出了3D-GPR(Grad Position-based Routing)算法，但没有考虑3D-WSN中的空洞问题，其实质仍然是贪婪算法。节点能量的耗尽是引起网络空洞的重要原因，文献[10]中研究了节点的协作传输及能量效率，提高了节点的路由效率，但是没有从整体上平衡网络的能耗；文献[11]提出了 3D-CSR(Cell Space Routing)算法，该算法有效地提高了 3维空洞网络的发送率，在一定程度上平衡了整个网络的总能耗，但是没有从整体上提高能量效率。

本文在3维胞元空间模型的基础上提出了多层胞元通道模型，并提出了 3D-EEMCR算法。路由方面，通过定义主通道和辅助通道相互协作周边模式来绕过空洞区域；能量方面，算法权衡考虑节点的剩余能量和位置信息来自适应选举胞父节点。

2 算法模型

2.1 网络模型

2.1.1 3维胞元空间模型 3维胞元空间[11]的模型结构如图 1所示。节点通信半径为 r，且 r∈[0,Rmax],Rmax为节点的最大通信半径。节点 i的位置坐标记作(xi,yi,zi)，其所在胞元位置记作(XI,YI,ZI)，胞元的边长记作d。以X轴坐标为例，节点坐标与胞元坐

图1 3维胞元空间模型

标的换算方法如式(1)所示：

将不存在有效传感器节点的胞元定义为空洞胞元，否则为非空洞胞元。非空洞胞元中的胞父节点充当路由器功能，实现胞间路由；胞子节点仅能与本胞元内的胞父通信。

2.1.2 多层胞元通道模型 定义多层胞元通道模型如下：

(1)主通道(Main Channel, MC)：路由模式由贪婪(greedy)模式转换为周边(perimeter)模式时，局部最小节点P所在的胞元层，即W=WP。

(2)辅助通道(Assistant Channel, AC): W=WP+1和所在的胞元层，并分别记作上层辅助通道(ACA)和下层辅助通道(ACB)。

(3)消息包传递法则：当前节点 C位于主通道(MC)时，消息包可以传递至主通道的其它节点或辅助通道的节点；当前节点C位于辅助通道(AC)时，消息包可以传递至本辅助通道的其它节点或主通道中的节点，为了避免形成死回路，当消息包传递至另一层辅助通道或其它3层通道外的节点时直接丢弃该消息包，如图2所示。

(4)主通道优先法则：当用逆时针法则选择下一跳胞元时，若主通道和辅助通道中的胞元同时满足要求，则优先选择主通道上的胞元作为下一跳胞元。

(5)辅助通道距离优先法则：当用逆时针法则选择下一跳胞元时，上下两个辅助通道中的胞元同时满足要求，则选择距离目的胞元较近的一个通道上的胞元作为下一跳胞元。

图2 消息包传递法则

2.2 节点能耗模型

根据自由空间中的通信模型[12]，当消息包大小为q bit，当前节点C的下一跳节点为N，则节点C的发射能量表达式如式(2)所示：

3 3D-EEMCR算法

3.1 自适应胞父选举机制

算法初始化时，各节点根据式(1)将所有胞元位置相同的节点自动成簇，并指定本胞元内初始能量Eint最大的节点作为胞父节点。

当胞父的剩余能量Eres下降至αEint或时，则由胞父节点触发选举。其中为低能量阈值系数，为死亡阈值系数。胞父触发选举后，首先根据胞元中节点的剩余能量 Eres确定候选胞父节点，然后根据所有候选胞父节点自身的剩余能量 Eres和节点位置来选择合适的节点作为胞父节点。假设本胞元内有m个候选胞父节点，该胞元的邻居胞父个数为 n，则定义胞父选举变量为 G，其表达式为

3.2 胞元路由机制

路由模式包括贪婪模式和周边模式，其初始化模式为贪婪模式。当消息包传递至局部最小节点时，路由模式切换至周边模式。

3.2.1周边模式初始化 路由模式换至周边模式时，需对重要参数作如下初始化：

返回贪婪模式判据：进入周边模式时，计算局部最小节点P所在胞元坐标到目标节点D所在胞元坐标的距离，记作。若，则消息包返回贪婪模式。

图3 胞父选举流程图

确定主通道(MC)：消息包传至局部最小节点P，计算P节点所在胞元位置(UP,VP,WP)与D节点所在胞元位置(UD,VD,WD)的坐标差值，记作(UPD,VPD,WPD)，选取差值最小坐标轴的P点坐标作为主通道胞元层，如图4所示。

图4 主通道胞元层选定

环路判据(P, Q)：由主通道的定义可知局部最小节点P位于主通道胞元层中，当为主通道胞元层时，以P为轴，PD在UOW面的投影P'D'为旋转边做逆时针旋转。逆时针旋转至第1个非空洞胞元即为下一跳胞元，其胞父节点记为 Q，若主通道和辅助通道的胞元同时满足要求，则遵循主通道优先法则和辅助通道距离优先法则。当再次依次经过(P, Q)节点时，立即丢弃该消息包；

3.2.2 多通道逆时针法则 多通道逆时针法则的一般过程：

(1)确定当前节点C的位置，并根据多通道模型中消息包切换规则确定下一跳胞元所在的胞元层。将可能的下一跳胞元层等效为单层通道；

(2)将当前节点C的前一跳节点记作A，逆时针法则以C为轴，CA在通道面上的投影C'A'为旋转边做逆时针旋转，旋转至第1个非空洞即为下一跳胞元，当主通道和辅助通道的胞元同时满足要求时，则遵循主通道优先法则和辅助通道距离优先法则；

4 仿真实验与结果分析

4.1 仿真环境及参数设置

本节利用 OMNeT++V4.1平台对算法进行仿真。节点布置的区域设置为体积为160 m×160 m ×160 m的立方体，其中胞元边长d为20 m，最大通讯半径Rmax为69.3 m，每个胞元中的节点数N在[0,随机产生。传输放大系数设为，发送单位数据包的电路损耗EELEC为50 nJ/bit，数据处理能耗EC为10 nJ，权重η和λ均设为0.5。每个消息包源节点和目的节点的个数均设为1，大小设为 1 bit，在消息包丢弃时产生新的消息包。在仿真实验中，通过构造不同体积的中心空洞区域(空洞区域没有传感器节点)和不同密度的节点分布，以检验 3D-EEMCR算法在不同环境下的消息包发送率，平均能耗以及网络的存活率。

4.2 仿真结果分析

3D-EEMCR, 3D-GPR和3D-CSR的消息包发送率随空洞体积变化的曲线对比如图6所示。在图6(a)，图6(b)和图6(c)中，设单个胞元内的节点数N为0或1，其中取N=1的概率分别为0.75, 0.67, 0.50。在图6(a)和图6(b)中，节点的密度较大而网络中的随机空洞较少，由于 3D-EEMCR算法使用多层胞元协作路由来绕过空洞区域，致使其发送率始终维持在95%以上；而3D-CSR算法使用单层胞元结构的周边模式，故消息包发送率较 3D-EEMCR算法下降了5%~15%；而3D-GPR算法遇到局部最小节点就丢包，所以其消息包发送率最低，并随空洞体积增大呈现直线下降的趋势。在图 6(c)中，节点的密度较小而网络中的随机空洞较多，故3种算法的发送率均有较大程度的下降，但是 3D-EEMCR算法的发送率较其它两种算法依然有明显的优势。

平均能耗是指网络总能耗与成功发送的消息包个数之比。3种算法的平均能耗随空洞体积的变化曲线对比如图7所示。在图7(a)中，随着空洞的不断变大，3D-CSR算法的单层胞元结构的周边模式将会失效而产生一定数量的丢包，而 3D-EEMCR将通过多层胞元结构协作路由来继续传递数据包，所以其平均能耗较高；由于3D-GPR算法遇到局部最小节点就选择丢包，所以其平均能耗最低。在图7(b)中，网络的节点密度较大，几乎所有消息包均可通过贪婪模式进行传递，所以3种算法的平均能耗基本相同。在图7(c)中， 3D-EEMCR和3D-CSR将定期选取胞父节点且消息包均可通过贪婪模式进行传递。3D-EEMCR算法选举位置更合适的节点作为胞父节点，根据式(2)，其在传递消息包时的单跳能耗最低，故其平均能耗最低；而3D-CSR算法比3D-GPR算法需额外消耗能量用于胞父选举，故其平均能耗最高。

图5 多通道逆时针法则

图6 3D-EEMCR, 3D-CSR和3D-GPR发送率对比

图7 3D-EEMCR, 3D-CSR和3D-GPR平均能耗对比

3D-EEMCR, 3D-GPR和3D-CSR 3种算法的节点存活率随时间的变化曲线对比如图8所示。在图8(a)，图8(b)和图8(c)中，由于3D-EEMCR和3D-CSR具有自适应选举机制来动态地平衡能耗，所以其节点的存活率比3D-GPR高，且随着胞元内节点数目N的增加，效果越来越明显；同3D-CSR算法相比，在选取胞父节点时，3D-EEMCR不仅考虑到节点的剩余能量，还将节点的位置信息作为参考量，故其节点的存活率更高。

5 结束语

图8 3D-EEMCR, 3D-CSR和3D-GPR存活率对比

本文提出的 3D-EEMCR算法采用了主通道和辅助通道相互协助的周边路由模式，依据主通道优先和辅助通道距离优先等法则，有效地提高了消息包的发送率；同时，该算法提出的自适应胞父选举机制权衡考虑了节点的剩余能量和位置因素，从而较好地实现了整个网络的能量均衡，降低了每轮的能量损耗，延长了整个网络的生命周期。仿真结果验证了 3D-EEMCR算法的正确性，并表明其比3D-CSR和3D-GPR更具优势。

[1] Losilla F, Garcia-Sanchez A J, García-Sánchez F, et al.. On the role of wireless sensor networks in intelligent transportation systems[C]. Transparent Optical Networks(ICTON), Coventry, UK, 2012: 1-4.

[2] Hussain R, Sahgal J L, Mishra P, et al.. Application of WSN in rural development, agriculture water management[J].International Journal of Soft Computing and Engineering(IJSCE), 2012, 2(5): 2231-2307.

[3] Lanjwar Namita and Nitnaware Dhiraj. Performance analysis of routing protocols for battlefield monitoring system[J].International Journal of Scientific Engineering and Technology, 2012, 1(2): 55-58.

[4] Goyal D and Tripathy M R. Routing protocols in wireless sensor networks: a survey[C]. Advanced Computing ＆amp;Communication Technologies (ACCT), Rohtak, Haryana,2012: 474-480.

[5] 余勇昌, 韦岗. 无线传感器网络路由协议研究进展及发展趋势[J]. 计算机应用研究, 2008, 25(6): 1616-1621.Yu Yong-chang and Wei Gang. Survey on routing protocols for wireless sensor networks[J]. Application Research of Computers, 2008, 25(6): 1616-1621.

[6] Rahman M A, Anwar F, Naeem J, et al.. A simulation based performance comparison of routing protocol on mobile Ad-hoc network (proactive, reactive and hybrid)[C].International Conference on Computer and Communication Engineering(ICCCE 2010), Kuala Lumpur, Malaysia, 2010:11-13.

[7] Fin G. Routing and addressing problems in large metropolitan-scale internetworks[R]. Technical Report ISU/RR-87-180,USC ISI, Marinadel Ray, California, 1987.

[8] Choi Moonshik and Choo Hyunseung. Bypassing hole scheme using observer packets for geographic routing in WSNs[C].ICOIN 2011, Barcelona, Spain, Jan 26-28, 2011: 435-440.

[9] Khaled D, Bassel A, Abderezak T, et al.. A 3D grid position-based routing protocol for mobile Ad-hoc networks[C]. Proceedings of the International Conference on Computer and Communication Engineering, Kuala, Lumpur,2008: 151-156.

[10] 王绍青, 聂景楠. 无线传感器网络中增加协作传输及其能量效率研究[J]. 电子与信息学报, 2010, 32(3): 759-762.Wang Shao-qing and Nie Jing-nan. Research on incremental cooperation transmission and its energy efficiency in wireless sensor networks[J]. Journal of Electronics ＆amp; Information Technology, 2010, 32(3): 759-762.

[11] 柯涛, 孙晖, 刘俊延. 基于三维胞元空间的无线传感器路由算法[J]. 电子与信息学报, 2013, 35(6): 1298-1304.Ke Tao, Sun Hui, and Liu Jun-yan. A wireless sensor network routing algorithm based on 3D cell space[J]. Journal of Electronics ＆amp; Information Technology, 2013, 35(6):1298-1304.

[12] Wendi Rabiner Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks[C]. System Sciences, Maui,Hawaii, Jan. 4-7, 2000: 1-10.