无线传感器网络中分簇定向扩散路由协议研究

高景菊,张文娟,谭永杰

(周口师范学院计算机科学与技术学院,河南周口466001)

在无线传感器网络中,路由协议的设计对网络通信的能量消耗有着重要影响。当前,对无线传感器网络路由协议的研究从网络拓扑结构上讲主要分为两个方面:平面路由协议和分簇路由协议[1,2]。在平面路由协议中,各个节点之间没有等级结构,平等的节点之间通过平面路由算法形成路由机制。典型的平面路由协议有Flooding协议及Gossiping协议[3],DD(Driected Diffusion)协议[4,5],Runor协议[6],SPIN(sensor protocol for information via negotiation)协议[7],SMECN(small minimum energy communication network)协议[8],GEM(graph embedding)协议[9],GEAR(geographical and energy aware routing)路由协议[10]。平面路由协议具有简单、健壮性好、不需要维护拓扑结构的优点。分簇路由机制中节点分为簇头节点和普通节点。由于分簇路由机制中具有便于管理,数据融合等优点,成为当前无线传感器网络中的研究热点。典型的分簇路由协议有LEACH(Low Energy Adaptive Clustering Hierarchy)[11],GAF(geographical adaptive fidelity)算法[12],最小ID算法(LID)[13],等。

本文在典型的平面路由协议DD的基础上,结合分簇机制,提出一种基于分簇的DD协议(CDD),并根据不同的应用,详细说明其工作原理,并仿真证明其有效性。

1 研究现状

无线传感器定向扩散路由协议(Driected Dif-fusion)[4,5]是一种典型的以数据为中心的框架性路由协议。为了在相应区域内查找汇聚节点(sink节点)感兴趣的事件,首先由汇聚节点发出查询消息,此消息即是汇聚节点感兴趣的事件的一串属性值。该消息由汇聚节点发出,通过洪泛方式传播给传感器节点。当传感器节点收到这个消息时,先查看自己的存储器里有没有相应的属性值。如果没有,则加入;如有,则更新。在消息洪泛的过程中,节点记录梯度信息(即自己接收到的消息是从哪个节点传播过来的),当消息传播结束后,传感器节点沿传播兴趣消息的反方向(根据梯度信息)进行数据传输。为了选择最优路径进行较快的数据收集,在DD中,采用路径加强的方式,即选择适当的方式加强收集消息的某些路径(部分路径失效),从而达到快速高效收集消息的目的。DD是周期性的协议,其周期性表现在sink节点周期性地向传感器节点发送广播兴趣。

概括来说,定向扩散路由协议的工作过程分为“兴趣扩散-梯度建立-路径加强”三个阶段[4,5](如图1所示)。兴趣扩散阶段采用洪泛方式进行;梯度建立依据兴趣扩散的路径完成;路径加强在消息传递过程中由各个节点(包括汇聚节点和传感器节点)之间相互作用完成。DD中仿真采用的方式是节点选择最先接收到传来兴趣消息的节点作为一个加强的路径。

图1 定向扩散的简单示例

从DD协议的工作过程可以发现,在DD协议中,在兴趣扩散阶段,传感器网络为传播兴趣消息要消耗大量能量,而在路径加强阶段,由于节点之间要传递控制消息(要加强路径的消息或者使某个路径失效的消息)也要消耗较多的能量。由于节能是无线传感器网络的重要指标,因此无线传感器网络的设计必须把节省能量放在重要位置。

目前,已提出了多个DD协议的改进协议。对DD协议的改进主要是基于减少DD协议在“兴趣扩散-梯度建立-路径加强”三个阶段的能量消耗。其中一类是不改变整个通信的拓扑结构,主要从减少DD协议中洪泛方式传播兴趣消息的能量消耗出发,来减少兴趣扩散阶段的能量消耗,其中文献[14-17]都是采用这种方式;另一类是不改变网络的拓扑结构,省略梯度建立和路径加强阶段,即定向扩散完成后即形成了数据传递的路径,文献[18,19]即是采用这种方式;还有一类就是改变网络的拓扑结构,采用分簇的方式对DD协议进行改进,其中大部分都是采用被动分簇方式。即初始状态下传感节点地位平等,随着兴趣消息的扩散采用不同的机制形成簇结构,这样形成的簇主要是来传播传感器收集到的信息[20,21],显然并没有节省兴趣扩散阶段的能量。文献[22]采用主动分簇的方式,结合DD和LEACH,其通信方式为“形成簇结构-兴趣扩散-梯度建立-路径较强”四个阶段,相对DD而言,其能量节省主要在兴趣扩散阶段和数据传输时。文献[22]没有考虑如果事件只是在整个网络部署区域中的一小部分区域发生,也没有考虑路径加强阶段的能量消耗。还有其他的改进方法,如通过决策函数选择转发点的协议[23],通过调整剩余能量的阈值限制低能量节点加入路径[24],等。

本文提出了对定向扩散路由协议的改进算法。该算法结合定向扩散路由协议的特点,在分簇机制下对定向扩散路由协议的通信机制进行改进,不同于其他以分簇方式对DD协议进行改进的方法。本协议采用主动分簇方式,且考虑事件的发生情况,简化通信机制的形成,以减少整个通信过程中的能量消耗,仿真证明了算法的有效性。

2 分簇定向扩散路由算法

由于DD是以数据为中心的路由协议,假设事件只发生在某一个相关区域之内。我们知道,sink节点感兴趣的只是和自己发出的兴趣消息相匹配的信息,而对于没有收集到该兴趣消息的节点,完全可以不理会相关事件的发生进入休眠状态,从而达到节省能量,延长网络的生命周期的目的。

图2 事件图

图2中灰色的节点为能收集到sink感兴趣信息的节点,而其余节点都是不能收集到sink感兴趣信息的节点。我们知道,如果按照DD的工作方式,经过洪泛的方式进行兴趣扩散,那么,每个节点都要进入活动状态来匹配兴趣消息和信息的收集,这样会消耗大量能量。另外,不论以何种工作方式,如果所有节点的接受兴趣消息也将有相应的能量消耗。

本文选择GAF的改进算法[25]来生成簇。由于GAF算法没有给出具体的路由过程,我们将以其思想进行路由传输(具体过程如图3所示)。由于在DD算法中,每个传感器节点都携带有GPS定位系统,目的是要收集检测区域的数据,而GAF算法是基于地理位置单元格划分的经典算法。DD算法和GAF算法都是对地理位置有较大要求的算法,在这个方面DD算法和GAF算法是一致的。GAF算法适用于规模和密度比较大的传感器网络中,在进行簇头选取的时候采取GAF的改进算法比较合理。所以,从图3可以看出,大部分节点的这种工作是没有必要的。下面将从这种思想出发,提出我们的算法。图3为CDD算法的执行过程图。

算法描述如下:

1 )簇生成。在形成簇结构的阶段,要选择GAF的改进算法形成簇结构。如图3中1)所示,其中A、B、C、D、E、F、G、I为簇头节点。

2 )将sink节点发出的兴趣消息沿簇头节点进行传播,如图3中2)所示。

3 )等待一定的时间,若有簇头节点和相应兴趣消息匹配的数据,该簇头节点在其通信范围内向周围节点广播该兴趣消息,如图3中3)所示。

4 )所有收到兴趣消息的节点和簇头节点进行信息收集,收集到的数据按照簇结构进行传送,如图3中4)所示。

在第1)步时,如无簇头节点和相应兴趣消息匹配的数据,则所有簇头节点向其簇内进行兴趣消息广播,所有簇内节点接收到相应消息后进行。若有相匹配的信息,则进行信息收集并把收集到的信息传给簇头,簇头节点负责把数据传给sink节点。其工作原理如图3所示。

在本算法中,簇的形成是周期性的。

本算法主要考虑事件只在一部分小区域内发生的情况下,相对于DD协议来说,其优势主要在于大大减少了洪泛方式进行兴趣传播的能量消耗,也省去了梯度建立和路径加强方面的能量消耗。该算法的能量消耗主要在成簇阶段,但相比DD算法仍能节省较多能量。如无簇头节点和相应兴趣消息匹配的数据则所有簇头节点向其簇内进行兴趣消息广播时,即可能监测到时间的节点都是非簇头节点,那么进行广播兴趣消息的做法可以确保监测事件能传给sink节点。该算法仍有不足之处,例如如果能感知到兴趣消息事件的节点分布的区域较大时,CDD算法对于DD算法优越性不强且可靠性不强,这方面有待于进一步地研究。

3 仿真实验

如下设置仿真环境:将600个传感器节点放置在坐标(0,0)到(600X600)m2的正方形区域内,节点携带GPS定位系统,初始能量都设置为2J,sink节点位于检测区域之外位置为(610,300)m的位置,节点的能量模型参考如下:

仿真主要从能量消耗和节点的存活个数两个方面对传统的DD协议和CDD协议进行比对,如图4和图5所示。

仿真结果表明,在传输相同数据时,CDD协议比传统DD协议的能量消耗有所降低,传输相同数据后CDD协议比传统DD协议的节点存活个数也相应较多。

表1 参数表

4 总结

本文在对定向扩散路由算法(DD算法)分析的基础上,引入主动分簇的思想对该算法进行改进并对改进的算法进行了详细的描述。仿真证明改进CDD算法比传统的DD算法在传输相同的数据任务时能量消耗小,节点存活个数多。该算法适合于兴趣区域范围较小的情况下,对算法进行扩展是下一步要研究的一个方向。

[1]孙利民,李建中,陈渝,等.无线传感器网络[M].北京:清华大学出版社,2005:2-15.

[2]沈波,张世永,钟亦平.无线传感器网络分簇路由协议[J].软件学报,2006,17(7):1588-1600.

[3]HAAS Z J,HALPERN J Y,LI Li.Gossipb-ased Ad hoc routing[C]//Proc of IEEE INFOCOM.New York: IEEE Communications Society,2002:1707-1716.

[4]Intanagonwiwat C,Govindan R,Estrin D,et al.Directed Diffusion for Wireless Sensor Networking[J].IEEE/ ACM Trans on Networking.2003,1l(1):2-16.

[5]Intanagonwiwat C,Govindan R,Estrin D.Directed Diffusion:A Scalable and Robust nununication Paradigm for Sensor Networks[C]//Proc of the 6th Annum ACM/ IEEE lnt1'Conf on Mobile Computing and Networking, 2000:56-67.

[6]Braginsky D,Estrin D.Rumor routing algorithm for sensor networks[M]//Proc.of the 1st Workshop on Sensor Networks and Applications.Atlanta:ACM Press,2002:22-31.

[7]KULIK J,HEINZELMAN W R,BALAKRISHNAN H.Negotiation-based protocols for disseminating information in wireless sensor networks[J].Wireless Networks,2002,8(2/3):169-185.

[8]LI Li,HALPERN J Y.Minimum energy mobile wireless networks revisited[C]//Proc of IEEE International Conferenee on Communications.Piscataway:IEEE, 2001:278-283.

[9]NEWSOME J,SONG D.GEM:graph embedding for routing and data centric storage in sensor networks without geographic information[C]//Proc of the 1st ACM Conf on Embedded Networked Sensor Systems, 2003:76-88.

[10]Yu Y,Estrin D,Govindan R.Geographical and energyaware routing:a recursive data dissemination protocol for wireless sensor networks[J].UCLA Computer Science Department Technical Report UCLA/CSD-TR-01-0023,los angeles:University of California,2001:1-11.

[11]Heinzelman W,Chandrakasan A,Balakrishnan H. Application-specific protocol architecture for wireless microsensor networks[C]//EEE Transaction on wireless communications,2002,1(4):660-670.

[12]Xu Y,Heidemann J,Estrin D.Geography-informed energy conservation for ad hoc routing[C]//Proceedings of the 7th Annual ACM/IEEE International Conference on Mobile Computing and Networking(Mobi-Com'01)Rome,2001:70-84.

[13]Ephremides A,Wieselthier J E,Bader D J A.Design concept for reliable mobile radio networks with frequency hopping signaling[J].Proceeding of IEEE,1987,75 (1):56-73.

[14]李应娣,单志龙.无线传感器网络定向扩算路由协议研究[J].计算机技术与发展,2010,20(9):40-43.

[15]赵奇,王汝传,孙力娟.传感器网络定向扩算协议研究及改进[J].计算机工程与设计,2007,28(12):2825-2828.

[16]李戈阳,曹阳,马曦.基于遗传优化的无线传感器网络定向扩散协议[J].湖南大学学报,2009,36(9):84-86.

[17]Miresmaeil Mirnbibaboli,Mehdi Mirfattahi,Mher Markosyan.Improving the Directed Diffusion in Order to Reduce the Average of Energy Consumption in Wireless Sensor Network[C]//the fifth international conference on sensor technologies and applications,IARIA,2011: 223-228.

[18]万健,吴建荣,徐向华.无线传感器网络定向扩算路由协议研究[J].计算机工程与科学,2009,31(6):99-102.

[19]SCHURGERS C,SRIVASTAVA M B.Energy efficient routing in wireless sensor networks[C]//Proc of Communications for Network.Centric Operations:Creating the Information Force,2001:357-361.

[20]Vlado Handziski,Andreas Kopke,Holger Karl.Improing the Energy Efficiency of Directed Diffusion Using Passive Clustering[C]//In Proc.of 1st European Workshop on Wiress Sensor Networks:Berlin,2004:172-187.

[21]李桂青,高仲合,王楠楠.基于簇头集的无线传感器网络定向扩散协议[J].山东大学学报,2010,45(11):37-42.

[22]CUI Yanrong,CAO Jiaheng.An improved Directed Diffision for wireless sensor networks[C]//Wireless Communications,Networking and Mobile Computing, shanghai,2007:2380-2383.

[23]骆海燕,郑淑丽,李少林.一种改进的无线传感器网络定向扩散协议[J].合肥工业大学学报,2010,33(6):851-854.

[24]仲盈,冯金鑫,熊庆旭.确定性无线传感器网络定向扩散路由协议[J].北京航空航天大学学报,2007,33(10): 1230-1232.

[25]Sami P,Simon J.Silence Is Golden with High Probability:Maintaining a Connected Backbone in Wireless Sensor Networks[C]//Wireless Sensor Networks:First EuropeanWorkshop.Berlin,Germany:EWSN,2004:106-118.