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