摘 要：無線傳感器網絡的路由協議是一個研究熱點。基于最小跳數的路由能夠保證網絡內部最小的消息包數量，協議容易實現，應用范圍很廣。本文從提高網絡的數據發送成功率出發，提出了一種基于可靠最小跳數場的路由協議，詳細介紹了可靠最小跳數場的建立過程以及路由的實現方法。TinyOS操作系統下的模擬實驗證實了協議的正確性。 關鍵字：無線傳感器網絡;路由協議;TinyOS操作系統 [b][align=center]Research on reliable routing protocol based on minimum hop field LI Liang, LIU Lin-Lan, SHU Jian, CHEN Ying[/align][/b] Abstract: routing protocol of wireless sensor networks （WSN） is an important hotspot. The routing protocol based on minimum hop can efficiently reduce the number of message into lowest, has the trait of easy implement and wide application. For the aim of increasing the packet success rate, this paper proposes a routing protocol base on reliable minimum hop field, particularly introduce the building process of the reliable minimum hop field and the routing method. Simulation in TinyOS operation system shows the correctness of our protocol. Keywords: wireless sensor network; routing protocol; TinyOS operation system 1. 引言 　　無線傳感器網絡由大量隨機布置在監測區域的傳感器節點自組織構成，能夠對環境實施實時監測，并以多跳的方式向用戶返回監測消息[1]。由于無線傳感器節點價格低廉，網絡能夠快速展開，具有抗毀性強的特點，因而在軍事偵察，環境監測，農業生產，建筑，工業生產控制上有著廣泛的應用前景。 　　路由協議是無線傳感器網絡中的一個重要的研究領域。文獻[2]對無線傳感器網絡中的路由協議有比較詳細的概述。由于傳感器節點存儲空間小、通信半徑短、計算能力和能量有限的特點[3]，因而在現有的節點硬件基礎上實現簡單且低能耗的路由協議是無線傳感器網絡研究的研究重點。文獻[4]從減少網絡內的消息數量出發，提出了基于最小跳的路由協議。監測區域中，處于不同區域的傳感器節點在節點通信半徑不變的情況下，以最優的方式（經歷的節點數最少），向匯聚節點發送數據。節點只需記錄一定數量大小的節點轉發集和自身的跳數，就可實現路由，協議實現簡單，能夠減少信息傳輸時延和減少網內信息數量，實現了網絡的低能量消耗。 　　然而，基于最小跳的路由協議存在一個明顯的不足，即沒有考慮到環境及節點自身因素的影響。在建立最小跳數場的過程中，兩個相鄰節點（跳數不同但在彼此的通信半徑之內），都建立起父子關系。而在實際情況下，由于環境影響及節點通信的不對等性，鏈路上的丟包率很大，節點間的鏈路通信質量很低。本文從提高網絡的包發送成功率出發，提出了一種基 　　于可靠最小跳數場的路由協議，采用通信鏈路質量進行評估的方式，在網內建立可靠最小跳數場。為驗證算法的可靠性，作者在TinyOS操作系統下，進行了一系列試驗，證明了算法的正確性。 2.TinyOS操作系統簡介 　　TinyOS操作系統是加州大學Berkeley分校專門為無線傳感器網絡開發的一種微型操作系統。它是一個適用于網絡化嵌入式系統的編程框架，通過在這個框架內鏈接一組必要的組件，就能方便地編譯出面向特定應用的操作系統，這對于存儲資源極為有限的系統來說是非常重要的。針對無線傳感器網絡節點眾多，以及多并發操作的工作方式，該操作系統采用了事件驅動的體系結構。無線傳感器網絡既具有多樣化的上層應用，又強調了系統的節能性要求，為此，系統采用既便于上層應用的開發，也有利于程序快速執行的模塊化設計方案。TinyOS操作系統具有以下特點：事件驅動的體系結構;單一的共享棧;無內核，無進程管理，無內存管理和無虛擬內存。 　　TinyOS操作系統由眾多組件構成，如主組件（main）、應用組件（application）、執行組件（actuating）、傳感組件（sensing）、通信組件（communication）和硬件抽象組件（hardware abstractions），在此基礎上用戶只需編寫相關的應用層組件即可，便于用戶利用已有組件開發新的應用，大大提高開發效率。 3.基于可靠最小跳數場的路由協議 　　基于可靠最小跳數場的路由協議包括兩個方面的內容：⑴在網內建立起可靠最小跳數場;⑵網內節點路由的實現。建立可靠最小跳數場又包含兩個方面的內容：⑴相鄰節點臨時父子關系的確立;⑵臨時通信鏈路的質量評估。 　　3.1 可靠最小跳數場的建立 　　3.1.1 相鄰節點臨時父子關系的確立 　　協議中的節點擁有唯一的網絡標識，并初始化匯聚節點的跳數為0，其余節點的跳數為一極大值。監測區域內網絡布置完畢后，匯聚節點向外廣播建立可靠最小跳數場的消息M，M包含以下三項內容： 　　Type; 消息的類型 　　ID; 節點的網絡標識 　　Hop; 節點當前跳數 　　網絡中的節點收到此類型消息后，啟動一個計時器Twait1，在該時間段內，節點持續接收此類消息。在計時器Twait1超時后，節點選取消息源節點中跳數最小的節點將作為臨時父節點并存儲臨時父節點的ID，同時置自身跳數為該最小跳數值加1。對于節點的臨時父節點，節點自身稱為臨時子節點。臨時父子節點的關系一旦確定，則稱它們之間的一條臨時通信鏈路已經建立起來了。 　　3.1.2 臨時通信鏈路的質量評估 　　臨時通信鏈路并不說明對應的兩節點能夠對等通信，也不能說明該臨時通信鏈路有比較高的通信質量。為此，協議使用質量評估的方法，測量臨時通信鏈路的數據發送成功率，從而達到對臨時通信鏈路的通信質量進行評估的目的。在評估過程中，具有較高數據發送成功率的臨時鏈路將被保留下來，成為固定鏈路，對應臨時父子關系變為正式父子關系;否則該臨時鏈路將被丟棄，對應的臨時父子關系亦被取消。 　　如圖1所示，節點1與節點2之間存在一條臨時鏈路，其中節點1為臨時父節點，節點2為臨時子節點。Twait1超時后，節點2啟動計時器T并向節點1發送N個測試消息。消息中包含自身ID，測試消息編號，節點所有臨時父節點的ID。臨時父節點接收到含有自身ID的測試消息后，啟動計時器Twait2，同時對收到的測試消息計數，得到計數值n。Twait2超時后，節點1向節點2發送帶有n值的返回消息。節點2將計算出到節點1的數據發送成功率Pt（n與N的比值）。當Pt大于等于閥值P時，它們之間的臨時鏈路將被保留成為固定鏈路，兩者形成正式的父子關系;如果T超時或Pt小于閥值P時該臨時，臨時通信鏈路將被取消。臨時父節點與臨時子節點的執行邏輯圖如圖1所示： [align=center] 圖1：節點執行邏輯圖[/align] 　　臨時通信鏈路質量評估后，新產生的子節點開始生成并向外廣播建立可靠最小跳數場的消息。所有已存在父子關系的節點將不再受理該消息，而所有沒有父節點的傳感器節點在收到該消息后，參與新一輪的建立可靠最小跳數場的操作。當網內所有節點的父子關系確定下來后，可靠最小跳數場的建立也宣告完成。 　　3.2協議路由的實現 　　可靠最小跳數場建立起來后，網絡中的每個節點都記錄了它的所有父節點。當有消息發送時，節點以輪詢的方式選擇自己的父節點作為下一跳。這主要基于兩個方面來考慮：⑴減少瓶頸的產生，當多個節點選擇相同父節點作為下一跳時，容易造成擁塞;⑵網絡負載平衡的需要，讓更多節點參與分擔能量消耗，避免單個節點的能量過快消耗而死亡。 4 模擬實驗及結果分析 　　作者在TinyOS操作系統下模擬建立最小跳數場的實驗。在閥值P不同的情況下，得到如圖2的一個拓撲關系圖。如圖2所示，節點0是匯聚節點，其余節點在它的通信半徑之內，在閥值較小的情況下，節點2、3、4、5的跳數為1，從而得到一個在閥值P為0.4時的拓撲圖。而當P為0.6時，節點4、5與匯聚節點的鏈路不符合要求，此時它們選擇了節點2、3為它們的父節點;在P為0.8時，節點2、3選擇節點1為它們的父節點。由此可知，在閥值P不同的情況下，網絡內的拓撲關系變化明顯。 　　本文也對建場過程中網絡的最大跳數以及消息到達網絡邊緣的時延之間的關系進行了分析和研究。時延的大小與節點跳數、節點對消息的處理時間、所設定的各種計時器有關。 [align=center] 圖2：不同閥值下網絡拓撲變化圖 圖 3：時延與跳數的關系圖[/align] 　　通過實驗，我們得出如圖3所示的一個關系圖。在Twait2不變的情況下，時延與Twait1的關系，當Twait1減小時，網絡的時延可以明顯減少。但是通過實驗得知，在Twait1很小的情況下，節點可能沒有收到具有最小跳節點發出的建立可靠最小跳數場的消息，因而網絡內拓撲變化很大，而當Twait1增大到一個定值后，網絡的拓撲變化將非常小。 [align=center] 圖4：不同閥值下匯聚節點收包情況[/align] 　　圖4說明的是在不同的閥值P的情況下，匯聚節點收到的數據包情況。網絡中的節點向匯聚節點發送一定數量的數據包。在閥值P增大的情況下，匯聚節點收到了更多的數據包，這也說明了在閥值P增大的情況下，數據包的丟失越少，從而也驗證了本算法的正確性。 5. 結論 　　人們已經在無線傳感器網絡路由協議方面做了很多卓有成效的工作，并已有許多切實可行的成果。本文在最小跳路由協議的基礎上，提出了一種基于可靠最小跳數場的路由協議，著重介紹了可靠最小跳場的建立過程，并對該過程中臨時父子關系的確立以及鏈路評估方法進行詳細的敘述。TinyOS操作系統下的實驗表明，基于可靠最小跳數場的路由協議在提高數據發送成功率上效果明顯。 　　論文創新點：1. 提出了可靠最小跳數場的概念并對可靠最小跳數場的建立進行了研究。 參考文獻 　　[1] 李建中,李金飛,石勝飛.傳感器網絡及其數據管理的概念、問題與進展[J].軟件學報， 2003,14（10）:1717～1727. 　　[2] 劉昌鑫,夏春和.無線傳感器網絡路由協議比較研究[J].微計算機信息,2006,9-1:02-05. 　　[3] 劉云璐,柴喬林,趙晉.無線傳感器網絡方向性分區路由算法[J]. 2006;1: 26. 　　[4] 馬祖長,孫怡寧.大規模無線傳感器網絡的路由協議研究[J].計算機工程與應用,2004:156. 　　[5] 孫利民,李建中,陳渝,朱紅松.無線傳感器網絡[M]. 清華大學出版社,2005.