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