文章快速检索  
  高级检索
基于3维胞元空间的MA并行能量高效路由
胡灿灿, 孙晖, 黄光群, 詹亚曙     
浙江大学电气工程学院, 浙江 杭州 310027
摘要: 针对无线传感器网络中移动代理在3维空间上的双向传输问题,提出了基于3维胞元空间的MA(mobile agent)并行能量高效路由算法(3D-PEMA).结合胞元空间模型和数据融合模型判断移动代理节点迁移时是否进行数据融合,提出了数据融合判定距离;同时在单层胞元系统中将派遣单MA和多MA的方法相结合,在MA双向并行路由算法(BPMA)基础上对其横向上的传输策略作了优化.仿真结果表明,3D-PEMA算法相比3D-BPMA和MIP(MultI-agent Planning)算法节省了网络的平均能耗,响应时间快,系统可靠性高.
关键词: 无线传感器网络     三维胞元空间     移动代理     数据融合     能量高效    
Parallel Mobile Agent Energy Efficiency Routing Based on 3D Cell Space
HU Cancan, SUN Hui, HUANG Guangqun, ZHAN Yashu     
College of Electrical Engineering, Zhejiang University, Hangzhou 310027, China
Abstract: Considering the problem of bidirectional parallel transmission of mobile agent (MA) in 3D space of wireless sensor networks, we propose a parallel mobile agent energy efficiency routing algorithm based on 3D cell space (3D-PEMA). We combines cell space model and data fusion model to judge whether MA performs data fusion when migrating to next node, and propose the data fusion judging distance. In single layer cell system, the algorithm optimizes routing strategy in horizontal plane based on bidirectional parallel MA routing algorithm (BPMA) with the combination of dispatching single MA and multiple MA. Simulation results show that compared with 3D-BPMA and multi-agent planning algorithm (MIP), 3D-PEMA algorithm effectively reduces the average energy consumption of network with fast response time, whosereliability is stronger.
Key words: wireless sensor network     3D cell space     mobile agent     data fusion     energy efficiency    

1 引言

随着科技网络水平的发展,无线传感器网络(WSN) 作为物联网底层网络的重要技术形式,已然成为学者的研究热点[1-2]. WSN有限的计算处理和能量供给的特点与传统的互联网技术有很大不同,其中无线传感器网络的路由技术显得尤为重要[3-5].文[6]中的LEACH (low-energy adaptive clustering hierarchy) 协议首次提出了数据聚合的层次路由概念,通过周期性按轮随机选举簇头的方法达到平衡网络节点能耗的目的.文[7]中的多条路由协议EBMH (Energy-Balanced Multi-Hop routing protocol) 在簇头选举时引入与节点能量有关的指数函数作为权值系数,并利用Dijkstra最短路径算法寻找最小能量传输路径.文[8]提出3维胞元空间模型,通过胞父自适应选举机制结合Greedy算法和右手法则,解决了无线传感器网络在3维空间下的成簇路由问题.

由于无线传感器网络的节点往往分布较密,其数据存在较大的相关性,目前众多基于移动代理的算法[9-11]可方便实现数据融合,从而降低数据冗余度、减少能耗.文[12]规划移动代理的迁移路径时考虑了节点的剩余能量和信息增益,减小了迁移成本从而降低网络能耗.当无线传感器网络的节点采集图像等信息时,其数据融合的开销已不能忽略[13],文[14]提出的MFST (minimum fusion Steiner tree) 算法着重强调了数据融合能耗,判断节点选择是否进行数据融合已达到更省能耗的效果.文[15]结合3维胞元模型和移动代理方法提出了基于3维胞元空间模型的MA双向并行路由算法(3D-BPMA),其3维空间的迁移路径问题划分成了多个单层平面问题,利用其在横向和纵向的双向传输达到提高效率、降低能耗的作用.本文提出基于3维胞元空间的MA并行能量高效路由算法(3D-PEMA),在3维胞元空间模型下引入数据融合判定距离,而且对3D-BPMA算法在横向上的传输策略作进一步的改进优化,达到节省能耗、减少响应时间的效果.

2 模型简介 2.1 3维胞元空间模型

本文采用3维胞元空间模型[8]划分整个无线传感器网络空间,见图 1.在该模型中,空间被严格分成了一块块立方体(胞元),每个胞元内的节点由胞父自适应选举机制[16]选出一个节点称为胞父,剩余的其它节点称为胞子.胞子仅参与胞元内节点的通信,胞父负责胞元间的通信.胞元的边长大小是由节点的通信能力所决定,Rmax表示节点最大通信半径,则为了保证相邻胞元的胞父能正常通信,应满足

图 1 3维胞元空间模型 Figure 1 3D Cell space model

在确定了胞元边长d后,胞元的坐标(XdYdZd) 与胞元内某节点的坐标(xiyizi) 存在以下映射关系:Xd=int (xi/d),Yd=int (yi/d),Zd=int (zi/d).

2.2 能耗模型

参考文[17]中的能耗模型,假设移动代理节点能耗E由数据融合能耗EF、数据传输能耗ETr和固定电路能耗EELEC三部分组成:E=EF+ETr+EELEC.

与传输能耗不同,数据融合能耗取决于融合前的数据大小[18]EF=(Qre+QpickKF,其中,Qre表示节点接收到的数据压缩包大小(bit),Qpick表示节点采集的数据包大小,KF为对单位大小数据进行融合所需的能耗(nJ/bit).

MA节点携带的数据包大小为Qma=Qcode+Qdata,其中,Qcode为代理节点初始化时程序的大小,在代理的整个生存周期中保持不变;Qdata为代理节点所携带的感兴趣数据大小,随着节点的迁移而递增.若用ρ(0≤ρ≤1) 表示数据融合率,代理节点从节点A迁移到节点B进行数据融合后,其携带数据包大小为

(1)

根据自由空间通信模型[6],传输能耗为

(2)

其中,r∈[0,Rmax]为两节点间的距离(m);p是固定常数,在自由空间模型中一般取p=2;KTr为在单位距离内发送单位大小数据包的电路耗能(nJ/(bit·m2)).

3 算法介绍 3.1 数据融合判定距离

考察移动代理在节点A处是否进行数据融合,假设节点B是移动代理下一跳节点.在节点能耗中固定电路能耗可忽略不计[19],则A节点的能耗情况如表 1所示.

表 1 节点能耗 Table 1 Energy consumption of the nodes
融合 不融合
EFA (QreA+QpickAKF 0
Qma (QreA+QpickA)×(1-ρ)+Qcode QreA+QpickA+Qcode
Qma×rAB2×KTr Qma×rAB2×KTr

根据表 1,计算融合和非融合下的能耗之差,得

(3)

其中rAB表示节点A和节点B之间的距离.由上述公式知,ΔE小于0,表明选择数据融合更省能耗.而ΔE的正负性取决于(KF-ρ×rAB2×KTr) 的正负,其中KFKTr为常数.在3维胞元空间模型下,胞父节点所产生的数据信息是融合了本胞元内所有胞子节点所采集的信息,因此移动代理由一个胞父迁移到相邻胞父所进行融合的数据信息是两个胞元内所有节点采集的信息总和,而不是两个胞父节点自身采集的信息.由于每个胞元大小相同、分布均匀,可假设相邻胞元所收集的数据信息差异性相同,故此处可假设代理节点迁移时数据融合率相同,此时令:

(4)

rF被称为数据融合判定距离,在3维胞元空间模型模型下为一固定的常数,如图 2.当rAB>rF时,ΔE < 0,此时节点应该选择进行数据融合,更省能耗;当rAB < rF时,ΔE>0,此时节点放弃数据融合.

图 2 胞父节点分布的两种情况 Figure 2 Two cases of the distribution of the cell father
3.2 单层胞元系统传输策略

在单层胞元系统模型中,空间的路由问题可简化成平面问题,此处仅讨论胞父位于胞元中心的网络能耗情况,并假设所有胞父节点所产生的感兴趣信息大小(Qt) 相等.在该简化处理下rAB>rF,因此后述两种传输策略的移动节点遍历完该层所有胞元时的数据融合能耗相同,所需比较的仅为传输能耗.根据文[20],从基站出发的移动代理节点离开第k个胞父节点后,其大小为

(5)

单层胞元系统模型中,邻居胞元分为边相邻邻居胞元和面相邻邻居胞元,见图 3.令Et=d2×KTr,则当传输大小相等数据时前者的胞父之间的传输能耗为后者的2倍.

图 3 单层胞元系统模型下的两种邻居胞元 Figure 3 Two kinds of neighbor cells under single cell system model
3.2.1 单移动代理遍历

基站只派出一个移动代理节点,该节点可采用图 4所示的方法收集完该层所有胞父节点信息,其传输能耗为

图 4 单移动代理遍历路径 Figure 4 Single MA transmission path

当所访问的单层胞元系统的胞元个数为奇数时,由染色原理容易证明移动代理节点想通过面相邻邻居胞元一次遍历所有胞元是不可能的,此时可以采用边相邻邻居胞元(在图 4的2维平面图中对应为对角正方形) 或者重复访问同个胞元的方法.这两种方法都会增大网络能耗,本文采用不采集离基站最远节点的方法,使得所访问胞元个数又为偶数,容易实现.

3.2.2 多移动代理遍历

在单层胞元系统中,将平面区域划分多个环形,第一个节点在最外环,如图 5所示.此时基站为每个环单独派送一个移动代理,为避免重复访问,内环的移动代理在经过外环的胞元时不收集数据信息.以图 5左图中的第2环为例,负责访问该环的移动代理完成任务时系统所需能耗包括3部分:将移动代理传递至内环能耗、内环遍历能耗、将移动代理返回至起点能耗,即:

图 5 多移动代理遍历路径 Figure 5 Multiple MA transmission path

据上述能耗计算方法,将每环的移动代理所迁移路径的能耗相加,即得到多移动代理遍历算法的总传输能耗:

同样,当所访问区域胞元为奇数时,为了节省能耗和便于管理移动代理迁移路径,不经过中心胞元.

3.2.3 传输策略

Qt=20 bit,Qcode=100 bit,ρ=0.8计算所访问不同数量胞元的单层胞元系统时的能耗情况,如表 2所示.

表 2 单层胞元系统传输能耗 Table 2 Transmission energy consumption in single cell system
胞元
个数
单移动代理遍历传输能耗
(Et单位)
多移动代理遍历传输能耗
(Et单位)
2×2 504 504
3×3 1 072 1 072
4×4 2 400 2 672
5×5 3 984 3 968
6×6 6 840 6 824
7×7 10 272 9 008
8×8 15 744 13 280
9×9 22 240 16 512
10×10 31 800 22 360
11×11 42 960 26 800
12×12 58 464 34 384

表 2结果知,在理想状态(胞父位于胞元中心,网络处于对称状态) 下,当移动代理节点所访问区域的胞元数目较小时,两种算法能耗差异较小;随着胞元数目的增多,多移动代理遍历的优势逐渐变大,能耗要降低很多.

但是上述的结果仅在单层胞元系统中,实际的MA并行能量高效路由算法是在整个3维空间运行,基站在一层胞元系统应尽量减少派遣的MA数量,否则过多的MA返回基站时会造成较大的延时和信道冲突.权衡MA数量和能耗情况,本文采取如下策略:当单层胞元系统中胞元个数小于等于5×5时,采用单移动代理遍历;否则选择多移动代理遍历.

3.3 算法流程

综上所述,本次3D-PEMA算法在3D-BPMA算法基础上增加了数据融合判定距离,并且对其横向传输策略作了优化,其在单层胞元系统运行流程如图 6所示.

图 6 单层胞元系统算法流程 Figure 6 Algorithm process in the single cell system
4 仿真实验 4.1 仿真参数设定

本文采用OMNeT++V4.1平台对算法的平均能耗和平均响应时间进行仿真验证,参数设定如表 3所示.

表 3 仿真参数 Table 3 Simulation parameters
参数名称 具体值
胞元边长d d=35 m~50 m
节点感应数据大小 20 bit
初始MA大小 100 bit
节点初始能量Ein Ein=200 J
固定电路能耗EELEC EELEC=2 nJ/bit
信号衰减常数KTr KTr=100 pJ/(bit·m2)
数据融合能耗KF KF=15 nJ/bit
低能量报警系数β β=0.3
MA的融合率ρ ρ=0.8
4.2 仿真结果分析

算法平均能耗仿真结果见图 7,3D-PEMA算法引入数据融合判定距离,实时地判别移动代理节点是否进行数据融合,使得两胞父距离较小时的胞间能耗更低.而3D-BPMA相比MIP算法,其发挥了胞元模型的优势,减少了MA的迂回路线,因此平均能耗要比MIP算法低.为了探索胞元规模对平均能耗的影响,在网络节点数目和网络空间大小不变的前提下改变胞元边长的大小.胞元边长从50 m改为35 m,此时胞元的体积缩小,每个胞元内的节点数变少,而整个网络空间的胞元数目变多,从图 7可以看出此时3D-PEMA和3D-BPMA算法的MA迁移路径上的胞元数均增多,因此其平均能耗变大.但是在胞元数目较多的情况下,3D-PEMA较3D-BPMA算法在横向上有着更合理的MA派遣机制,因此其节省能耗的优势更明显.

图 7 平均能耗对比 Figure 7 Contrast of average energy consumption

算法平均响应时间结果见图 8,3D-PEMA算法保留了3D-BPMA算法中MA双向并行传输的优势,因此其平均响应时间要比MIP算法短.随着胞元规模变大,3D-PEMA和3D-BPMA算法的迁移路径均变长,其平均响应时间也变大.由于3D-PEMA在大规模胞元下能合理地派遣多MA访问单层胞元系统,其平均响应时间较3D-BPMA算法的优势也更明显.

图 8 平均响应时间对比 Figure 8 Contrast of average response time

为了检测算法的可靠性,仿真进行了MA发送率的对比. MA发送率是指基站回收到的MA的数量与其发出的MA数量的比率,其值越大,表明MA派遣送回的几率越大,系统可靠性更高,如图 9所示. 3D-PEMA和3D-BPMA算法采用MA双向并行传输,使得MA迁移路径较短,节点丢包率更低,因此MA发送率更高.随着胞元规模的增大,3D-BPMA算法中的MA迁移路径增大明显,其MA发送率显著下降;而3D-PEMA由于横向上传输策略的适应性更强,其MA发送率影响不大.

图 9 MA发送率对比 Figure 9 Contrast of MA delivery rate
5 结论

本文充分结合了3维胞元空间模型和数据融合模型的特点,使得胞间的数据传输更省能耗.同时3D-PEMA算法在考虑到了每层胞元系统中胞元个数的差异性,引入了单MA遍历访问和多MA遍历访问相结合的方法,使得MA的派遣方式更合理,系统的能耗更低,响应及时,可靠性增加.进一步的研究计划是在胞元内实现胞父与胞子的通信算法优化.

参考文献
[1] Liu Q, Huang X H, Leng S P. Deployment strategy ofwireless sensor networks for Internet of Things[J]. China Communications, 2011, 8 (8): 111–120.
[2] Somov A, Baranov A, Savkin A, et al. Energy-aware gas sensing using wireless sensor networks[M]//Lecture Notes in Computer Science:vol. 7158. Berlin, Germany:Springer-Verlag, 2012:245-260.
[3] Goyal D, Tripathy M R. Routing protocols in wireless sensor networks:A survey[C]//2012 Second International Conference on Advanced Computing & Communication Technologies (ACCT). Piscataway, NJ, USA:IEEE, 2012:474-480.
[4] 余勇昌, 韦岗. 无线传感器网络路由协议研究进展及发展趋势[J]. 计算机应用研究, 2008, 25 (6): 1616–1621. Yu Y C, Wei G. Survey on routing protocols forwireless sensor networks[J]. Application Research of Computers, 2008, 25 (6): 1616–1621.
[5] 张乾, 沈颂. 基于无线传感器网络的物流自保护环形路由协议[J]. 信息与控制, 2014, 43 (2): 186–192. Zhang Q, Shen S. Ring protocol of self-protection in logistics based on wireless sensor networks[J]. Information and Control, 2014, 43 (2): 186–192.
[6] Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless microsensor networks[C]//The 33rd annual Hawaii international conference on System sciences. Piscataway, NJ, USA:IEEE, 2000:8020.
[7] 吕红芳, 张浩. 能量均衡的簇间多跳路由协议[J]. 信息与控制, 2014, 43 (3): 306–313. Lü H F, Zhang H. Energy-balanced multi-hop routing protocol among clusters[J]. Information and Control, 2014, 43 (3): 306–313.
[8] 柯涛, 孙晖, 刘俊延. 基于三维胞元空间的无线传感器路由算法[J]. 电子与信息学报, 2013, 35 (6): 1298–1304. Ke T, Sun H, Liu J Y. A wireless sensor network routing algorithm based on 3D cell space[J]. Journal of Electronics & Information Technology, 2013, 35 (6): 1298–1304.
[9] Qi H, Iyengar S S, Chakrabarty K. Multiresolution data integration using mobile agents indistributed sensor networks[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C:Applications and Reviews, 2001, 31 (3): 383–391. DOI:10.1109/5326.971666
[10] Dang X C, Hao Z J. A research of multiple mobile agents routing algorithm based on redundancy for wireless sensor network[C]//2013 International Joint Conference on Awareness Science and Technology and Ubi-Media Computing (iCAST-UMEDIA). Piscataway, NJ, USA:IEEE, 2013:740-747.
[11] Ota K, Dong M, Wang J, et al. Dynamic itinerary planning for mobile agents with a content-specific approach in wireless sensor networks[C]//72nd Vehicular Technology Conference Fall. Piscataway, NJ, USA:IEEE, 2010:1-5.
[12] Lohani D, Varma S. Mobile agent itinerary planning using analytic hierarchy process for wireless sensor networks[C]//2013 International Conference on Multimedia, Signal Processing and Communication Technologies (IMPACT). Piscataway, NJ, USA:IEEE, 2013:16-20.
[13] Luo H, Luo J, Das S K, and Liu Y. Energy efficient routingwith adaptive data fusion in sensor networks[C]//Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing. New York, NY, USA:ACM, 2005:80-88.
[14] Luo H, Liu Y, Das S K. Routing correlated data withfusion cost in wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2006, 5 (11): 1620–1632. DOI:10.1109/TMC.2006.171
[15] 黄光群, 孙晖, 路扬. 基于三维胞元空间的MA双向并行路由算法[J]. 传感器与微系统, 2015, 34 (7): 137–140. Huang G Q, Sun H, Lu Y. Bidirectional parallel mobile agent routing algorithm based on 3D cell space[J]. Transducer and Microsystem Technologies, 2015, 34 (7): 137–140.
[16] 刘俊延, 孙晖, 柯涛, 等. 基于三维胞元空间的能量高效性多通道协作路由算法[J]. 电子与信息学报, 2014, 36 (3): 744–748. Liu J Y, Sun H, Ke T, et al. Energy efficiency multi-channel coordination routing algorithm based on 3D cell space[J]. Journal of Electronics & Information Technology, 2014, 36 (3): 744–748.
[17] 胡海峰, 杨震. 无线传感器网络中基于移动代理的自适应数据融合路由算法[J]. 电子与信息学报, 2008, 30 (9): 2254–2258. Hu H F, Yang Z. Mobile-agent-based adaptive data fusion routing algorithm in wireless sensor networks[J]. Journal of Electronics & Information Technology, 2008, 30 (9): 2254–2258.
[18] Luo H, Luo J, Liu Y, et al. Adaptive data fusion for energy efficient routing in wireless sensor networks[J]. IEEE Transactions on Computers, 2006, 55 (10): 1286–1299. DOI:10.1109/TC.2006.157
[19] 孙利民, 李建中, 陈渝. 无线传感器网络[M]. 北京: 清华大学出版社, 2005. Sun L M, Li J Z, Chen Y. Wireless sensor networks[M]. Beijing: Tsinghua University Press, 2005.
[20] Chen M, Yang L T, Kwon T, et al. Itinerary planning for energy-efficient agent communications in wireless sensor networks[J]. IEEE Transactions on Vehicular Technology, 2011, 60 (7): 3290–3299. DOI:10.1109/TVT.2011.2134116
http://dx.doi.org/10.13976/j.cnki.xk.2017.0001
中国科学院主管,中国科学院沈阳自动化研究所、中国自动化学会共同主办。
0

文章信息

胡灿灿, 孙晖, 黄光群, 詹亚曙
HU Cancan, SUN Hui, HUANG Guangqun, ZHAN Yashu
基于3维胞元空间的MA并行能量高效路由
Parallel Mobile Agent Energy Efficiency Routing Based on 3D Cell Space
信息与控制, 2017, 46(1): 1-6.
Information and Control, 2017, 46(1): 1-6.
http://dx.doi.org/10.13976/j.cnki.xk.2017.0001

文章历史

收稿/录用/修回: 2015-11-23/2016-01-25/2016-04-22

工作空间