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