快速建立數據傳輸路徑的謠傳路由協議改進

徐晶，程良倫

廣東工業大學自動化學院，廣州 510006

快速建立數據傳輸路徑的謠傳路由協議改進

徐晶，程良倫

廣東工業大學自動化學院，廣州 510006

針對無線傳感器網絡謠傳路由協議（Rumor Routing Protocol，RRP）在生成數據傳輸路徑的過程中，消息傳播節點隨機選擇下一跳鄰居節點發送消息所形成的數據傳輸路徑可能出現回路現象、交叉現象以及查詢流量大等問題，提出一種改進的謠傳路由協議（NM-RRP），該協議通過在代理消息和查詢消息中記錄消息經過的節點及其鄰居節點來選擇下一跳節點，并且對消息傳輸經過節點的鄰居節點留下信息，避免隨機選擇節點發送消息。實驗證明，改進后的算法能有效避免消息在某個節點附近產生傳播、回路及交叉等現象，并能夠快速建立數據傳輸路徑。

無線傳感器網絡；謠傳路由協議；攻進的謠傳路由協議（NM-RRP）；傳輸路徑

1 引言

無線傳感器網絡是當前國際上備受關注的、知識高度集成的一個新興研究領域[1]，它由多個學科高度交叉組成，綜合了傳感器技術、嵌入式技術、嵌入式計算技術、現代網絡及無線通信技術、分布式信息處理技術等多個學科的知識，能夠通過各類集成化的微型傳感器節點協作完成監測、感知和采集各種環境信息或被監測對象的信息，并對信息進行處理，可以通過隨機自組織無線通信網絡以多跳中繼方式將所感知的信息傳送到用戶終端。路由協議作為無線傳感器網絡組網的基礎和網絡層的核心技術，成為無線傳感器網絡研究的重點。在無線傳感器網絡中，網絡拓撲結構的變化、路由信息的交換、最佳路由的選擇、目的節點的定位、產生和維護以及數據的轉發等操作都是由相應的路由協議來完成的。因此，無線傳感器網絡的系統設計是否合理有效，很大程度上取決于其路由協議的設計[2]。

根據路由協議的實現方法特點，無線傳感器網絡路由協議主要分為四類[3]：以數據為中心路由協議、基于聚簇的路由協議、基于地理位置路由協議和能量感知路由協議。以數據處理為中心的無線傳感器網絡具有節點數目眾多、攜帶能源受限以及通信距離受限等特點，在節點多、網絡地理位置未知的情況下，如何快速建立數據傳輸路徑成為無線傳感器網絡路由研究的重點問題。根據M onte-Carlo模型可知，在一個矩形區域中，兩條直線相交的概率接近70%，可計算出當目的節點發出五條路徑與源節點路徑相交的概率為99.7%，因而謠傳路由協議具有可行性[4]。Zhonghua Wang等人提出無線傳感器網絡能量聚簇謠傳路由協議[5]，該協議將能效及聚簇機制引入到謠傳路由中，并對整個網絡劃分成簇，消息的轉發將節點的剩余能量作為其中一個參考因子。該協議雖然可以快速建立數據傳輸路徑，但簇首節點存在能耗大等問題。Yanrong Cui等人提出一種新穎謠傳路由協議[6]，利用蟻群算法思想提出當下一跳節點已經在之前的傳輸過程中承擔過傳輸節點時，則選擇其他節點做下一跳節點。該協議可以有效地避免同一節點一直承擔消息轉發節點，但該算法終究不能避免回路現象。Shokrzadeh H等人提出基于重心設置的無線傳感器網絡謠傳路由協議[7]，該協議在網絡中設置重心區域，在建立數據傳輸路徑的過程中代理消息和查詢消息優先和重心區域的節點建立連接。該算法增大了代理消息和查詢消息相交的幾率，但在建立數據傳輸路徑的過程中仍無法避免交叉、回路現象。

本文在充分研究以數據為中心的謠傳路由協議的基礎上，針對謠傳路由協議在收發代理消息過程中由于回路、交叉現象而引起的網絡查詢流量大的問題，提出一種謠傳路由協議的改進算法（NM-RRP），該算法通過查詢消息及代理消息在其經過節點及其鄰居節點留下相關信息，在選擇下一跳節點時，若下一跳節點是同類消息經過節點或其鄰居節點則放棄該節點做下一跳節點；若下一跳節點不是同類消息經過節點或其鄰居節點，則將其作為下一跳節點；若某節點即是代理消息經過節點或其鄰居節點，又是查詢消息經過節點或其鄰居節點，則該節點主動發消息給其鄰居的代理消息節點及查詢消息節點，從而形成一條完整的數據傳輸路徑。

2 謠傳路由協議

謠傳路由協議的基本思想是：監測區域中的傳感器節點產生代理消息，代理消息隨機路徑向周邊傳播，同時匯聚節點也沿隨機路徑發送查詢消息。一旦代理消息和查詢消息的傳輸路徑交叉在一起，就形成了從匯聚節點到監測區域的一條完整數據傳遞路徑。如圖1所示。

圖1 謠傳路由協議的實現原理圖

從謠傳路由協議的工作過程可以看出，傳感器節點和匯聚節點隨機選擇的路徑信息在形成數據傳輸路徑的過程中很可能形成環路、交叉現象如圖2，在數據傳輸過程中造成節點消耗大，網絡壽命減小等問題。如果消息在傳輸過程中，節點可以根據鄰居節點記錄的消息經過情況來選擇下一跳節點，從而能有效地避免環路及交叉現象。

圖2 謠傳路由協議形成數據傳輸路徑過程出現回路示意圖

3 NM-RRP算法

3.1 NM-RRP算法思想

監測區域中的傳感器節點產生代理消息，節點從鄰居列表中隨機選擇下一跳節點傳播代理消息；在代理消息中加入當前傳播節點的ID、消息傳播的當前跳數、當前節點的鄰居節點ID及消息的生命值減少1。對鄰居節點廣播消息經過信息。

如圖3所示當代理消息經過節點1后，就在代理消息后增加一個鄰居列表，將代理消息經過節點1、當前代理消息傳播的跳數值6、鄰居節點2、5及消息的生命值減1，隨機選擇2號節點作為下一跳節點，并對鄰居節點5廣播消息經過。節點5收到節點1發送的消息后，記錄代理消息經過附近一次。消息經過節點2后，就在代理消息后增加一個鄰居列表，將代理消息經過節點2、當前代理消息傳播的跳數值7，隨機選擇代理消息中未登記的鄰居節點做下一跳節點，以此類推。

圖3 謠傳路由協議的實現原理局部圖

廣播代理消息的節點在選擇下一跳節點時，首先對比鄰居節點和代理消息中記錄的消息經過節點及其鄰居節點，如果某鄰居節點在消息記錄中不存在，則下一跳節點考慮該節點；如果所有鄰居節點在消息記錄中都存在，則下一跳節點考慮鄰居節點被消息記錄過一次的節點。對圖3而言，查詢消息到達節點2后，節點2通過查詢消息中的記錄判斷到鄰居節點3未記錄，則選擇節點3為下一跳節點。如果多個鄰居節點都不在消息記錄中，則隨機選擇這些鄰居節點做下一跳節點。對于匯聚節點發送的查詢消息也同樣適用以上思想。

3.2 改進后算法的具體執行過程

（1）每個傳感器節點維護一個鄰居列表和一個事件列表。

（2）若一個節點監測到一個事件發生，則在事件列表中增加一個表項用以設置事件名稱，并將該事件的跳數值設置為0，同時根據一定的概率產生一個代理消息。

（3）某節點收到代理消息后，檢查事件列表中是否存在查詢消息經過信息，若存在，則同時發送消息至鄰居的代理消息節點及查詢消息節點，通知數據傳輸路徑建立成功。若不存在，首先通過代理消息中的消息經過節點及鄰居節點列表，隨機選擇列表中不存在的鄰居節點作為下一跳節點；其次，該節點將代理消息的跳數值加1，將生命值TTL減1，并在消息中加入鄰居節點ID，組成新的代理消息后發送至下一跳節點；最后，該節點廣播消息經過信息至鄰居節點。

（4）當某節點收到鄰居節點發送的代理消息經過信息后，首先檢查事件列表中是否存在查詢消息，若存在，則同時發送消息至鄰居的代理消息節點及查詢消息節點，通知數據傳輸路徑建立成功；若不存在，則該節點在其事件列表中添加代理消息信息、經過的鄰居節點ID信息及其跳數值。

（5）網絡中的任何節點都可能產生一個針對特定事件的查詢消息。查詢消息經過的節點按照同樣方式轉發，并記錄該消息的相關信息。這個過程直到查詢的TTL值為0或是查詢到達了所期待的事件為止。

改進后的算法主框圖如圖4所示。

圖4 NM-RRP路由協議主框圖

首先將節點初始化后，如果有事件發生則進入代理消息選擇下一跳節點環節，如果沒有事件發生則繼續等待。確定下一跳節點后，進入同一個節點收到代理消息和查詢消息環節從而進行判斷，如果條件不成立，且消息跳數值不為0，則繼續進入查詢同一個節點收到代理消息和查詢消息環節。從圖4可以看出，NM-RRP算法主流程和RRP算法主流程基本相似，其中不同的是代理消息及選擇下一跳節點環節和同一個節點收到代理消息和查詢消息，如圖5，圖6所示。

圖5 代理消息及選擇下一跳節點框圖

圖6 同一個節點收到代理消息和查詢消息框圖

在圖5中，當節點收到代理消息后，在代理消息后端加入節點ID，并取出代理消息后端的節點鄰居列表，經過對比代理消息后端的消息經過的鄰居列表和節點的鄰居列表，選擇節點鄰居列表中節點在消息經過鄰居列表中出現次數最少的節點作為下一跳消息傳播節點。保存當前消息及其跳數到事件列表，并將事件列表發送給鄰居節點，通知鄰居節點消息經過。再加入當前節點的鄰居節點，并將其和之前取出的消息經過節點及其鄰居節點按出現次數由少至多進行排序。然后，將結果存入代理消息后端的鄰居列表中，同時消息的生命值減1，并存入代理消息中。

在圖6中，當傳播代理消息的節點收到查詢消息時，兩個消息都經過了同一個節點，此時，成功地形成了數據傳輸路徑。同樣，當傳播查詢的節點收到代理消息時，同樣成功地形成了數據傳輸路徑。當某個節點既收到了代理消息經過的信息，又收到了查詢消息經過的消息，說明代理消息和查詢消息都在該節點周圍，此時，該節點發送消息給代理消息傳輸節點即查詢消息傳輸節點，表示數據傳輸路徑已經建立。

3.3 改進后算法的性能分析

謠傳路由協議在轉發代理消息或查詢消息時都是采用隨機方式，每個鄰居節點被選作下一轉發節點的概率是相等的，所以發出的消息有可能在某幾個節點周圍，從而產生環路交叉現象，不利于消息傳播。最終導致增加查詢流量，查詢效率降低。改進后的謠傳路由算法將消息傳輸節點的鄰居節點用來記錄消息經過的信息。改進后網絡中的節點更具靈活性，當代理消息和查詢消息都在某個節點附近則會形成數據傳輸路徑，并且可以有效地避免消息在某個節點附近傳播，從而避免了回路及交叉現象的發生，減少了查詢流量，提高了查詢效率。

4 算法仿真

4.1 建立數據傳輸路徑

利用MATLAB平臺，建立一個50 m×50 m的方形區域作為無線傳感器網絡覆蓋區域，網絡中包含100個傳感器節點。為方便仿真初始化條件設置，節點之間相互均勻分布，如圖7所示。

圖7 仿真節點布置

分別利用謠傳路由協議（RRP）和改進的謠傳路由協議（NM-RRP）在仿真環境中進行數據傳輸路徑建立的實驗，其建立的數據傳輸路徑分別如圖8和圖9所示。

圖8 RRP建立數據傳輸路徑過程

從圖8可以分析出，傳統的謠傳路由協議在消息傳播節點只是隨機地選擇下一跳節點，將會產生擦肩而過的現象，造成查詢流量增多，網絡壽命減小。從圖9中可以看出改進后的算法在查詢消息和代理消息距離較近時，節點能夠主動連接形成數據傳輸路徑，有效地避免了查詢流量，這對整個網絡而言都是非常有利的。

圖9 NM-RRP數據傳輸路徑建立過程

4.2 網絡存活時間及能耗比較

通過對謠傳路由協議（RRP）、改進后的謠傳路由協議（NM-RRP）、文獻[4]中改進的謠傳路由協議（L-RRP）用文獻[8]中提供的能量損耗模型進行仿真。

網絡存活時間如圖10所示，網絡剩余能量如圖11所示。通過仿真結果可以看出改進后的謠傳路由協議相對于其他兩個路由協議更具優越性。

表1 仿真實驗主要參數

圖10 網絡存活時間比較

圖11 網絡剩余能量比較

5 結束語

本文通過對謠傳路由協議進行研究，發現其在建立數據傳輸過程中，消息隨機選擇節點發送，該模式在發送的過程中形成環路及在某個節點附近傳播的可能性較大，不僅造成數據傳輸路徑的形成過程緩慢，且流量消耗較大。針對上述問題，本文提出在消息傳輸經過節點的鄰居節點留下信息及在選擇下一跳節點時，判斷是否是之前經過的節點及鄰居節點，從而選擇下一跳節點，從而有利于消息的傳播及數據傳輸路徑的快速建立，并通過實驗仿真驗證了該算法的有效性。

[1]崔莉，鞠海玲，苗勇，等.無線傳感器網絡研究進展[J].計算機研究與發展，2005，42（1）：163-174.

[2]路綱，周明天，佘堃，等.無線傳感器網絡路由協議的壽命分析[J].軟件學報，2009，20（2）：375-393.

[3]唐勇，周明天，張欣，等.無線傳感器網絡路由協議研究進展[J].軟件學報，2006，17（3）：410-421.

[4]夏靜，莊雷，白雨，等.無線傳感器網絡謠傳路由研究及改進[J].微計算機信息，2007，23（19）：152-153.

[5]Wang Zhonghua，Chen Kai，Lin Mei，et al.Energy-efficient clustering rumor routing protocol for wireless sensor networks[C]//7th International Conference on Ubiquitous Intelligence&Computing and 7th International Conference on Autonom ic&Trusted Computing，2010：200-205.

[6]Cui Yanrong，Qin Hang.A novel rumor routing for wireless sensor network[C]//Fourth International Conference on Genetic and Evolutionary Computing，2010：795-797.

[7]Shokrzadeh H，Haghighat A T，Saadatmndi P，et al.Rumor routing by appointment in center of gravity in wireless sensor networks[C]//International Conference on Information Networking，2011：177-181.

[8]Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless m icrosensor networks[J].IEEE Transactions on W ireless Communications，2002，1（4）：660-670.

XU Jing,CHENG Lianglun

School of Automation,Guangdong University of Technology,Guangzhou 510006,China

Aiming at the loop,crossover phenomenon and the energy consumption problem can appear in the data transmission path formed from the message transmission chose the next-hop neighbor nodes randomly for sending messages, which occurrs in the data transmission process of rumor routing protocol（RRP）in wireless sensor networks.An improved rumor routing protocol,NM-RRP,is introduced,which can choose the next-hop node through the nodes and its neighbor nodes from the messages recorded by the agent messages and the inquired messages,then leave the information at the neighbor nodes around the node which message transmission has been passed by,thereby the random chose node is avoided to send messages.Experiments show that the improved algorithm can avoid the message producing the transmission loop and crossover phenomenon around the node effectively and can establish a data transmission path rapidly.

wireless sensor network;rumor routing protocol;NM-RRP;transmission path

A

TN919

10.3778/j.issn.1002-8331.1208-0233

XU Jing,CHENG Lianglun.Improved method for rum or routing protocol in establishing data transmission path rapidly.Computer Engineering and Applications,2014,50（16）：109-112.

廣東省重大科技專項（No.2011A 080802008）。

徐晶（1989—），女，碩士研究生，研究領域為無線傳感器網絡；程良倫，博士研究生導師。E-mail：398419925@qq.com

2012-08-19

2012-12-11

1002-8331（2014）16-0109-04

CNKI網絡優先出版：2012-12-20,http://www.cnki.net/kcms/detail/11.2127.TP.20121220.1652.008.htm l