金仁成，孟麗莎，韋 寧，李東旭

(大連理工大學(xué)，遼寧省微納米技術(shù)及系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116024)

0 引言

無(wú)線傳感器網(wǎng)絡(luò)(WSNs，wireless sensor networks)是由眾多具有傳感、數(shù)據(jù)處理和短距離無(wú)線通信能力的傳感器通過無(wú)線方式連接，相互協(xié)作，同物理世界進(jìn)行交互，共同完成特定的應(yīng)用任務(wù)。WSNs在軍事國(guó)防、環(huán)境監(jiān)測(cè)、生物醫(yī)療、搶險(xiǎn)救災(zāi)及商業(yè)應(yīng)用等領(lǐng)域具有廣闊的應(yīng)用前景[1]。

路由協(xié)議是無(wú)線傳感器網(wǎng)絡(luò)關(guān)鍵技術(shù)之一，無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議有多種分類方法，其中主動(dòng)型和按需型是最基本的分類方法[2]。主動(dòng)型路由繼承了傳統(tǒng)的距離矢量路由，但在消除路由環(huán)路和過期路由等方面做了適應(yīng)于自組網(wǎng)特性的改進(jìn)[3]。按需型路由協(xié)議中節(jié)點(diǎn)并不維護(hù)尚未需要的路由，因此所產(chǎn)生的路由控制開銷比主動(dòng)型協(xié)議少得多，更有利于擴(kuò)展推廣[4]。AODV路由協(xié)議屬于典型的按需型路由協(xié)議，易于實(shí)現(xiàn)[5]，但是傳統(tǒng)的 AODV存在能耗大、較易產(chǎn)生通信沖突等不足，本文針對(duì)這些不足提出了改進(jìn)方案，并在自主開發(fā)的ZigBee節(jié)點(diǎn)平臺(tái)上進(jìn)行了相應(yīng)的性能測(cè)試。

1 AODV路由協(xié)議

AODV[6]路由協(xié)議(Ad-Hoc On-Demand Distance Vector Algorithm)是最經(jīng)典和最廣泛被研究的按需路由協(xié)議之一。當(dāng)一個(gè)節(jié)點(diǎn)需要到達(dá)目的節(jié)點(diǎn)的路由時(shí)，啟動(dòng)一個(gè)路由發(fā)現(xiàn)過程，廣播路由請(qǐng)求消息(RREQ，route request)。中間節(jié)點(diǎn)收到這個(gè)路由請(qǐng)求消息時(shí)若有RREQ所查找的有效路由，或者就是目的節(jié)點(diǎn)，就產(chǎn)生并發(fā)送路由應(yīng)答消息(RREP，route reply)返回路由發(fā)起節(jié)點(diǎn)。路由建立后，路由中的每個(gè)節(jié)點(diǎn)在規(guī)定的有效時(shí)間內(nèi)，都要維護(hù)活動(dòng)路由的下一跳和上一跳信息，直到該路由不再被使用而刪除相關(guān)信息。路由中的每個(gè)節(jié)點(diǎn)都保留了一個(gè)路由表，該路由表保存了到達(dá)目的節(jié)點(diǎn)的路由中把自己作為下一跳節(jié)點(diǎn)的相鄰節(jié)點(diǎn)。在AODV協(xié)議中，源節(jié)點(diǎn)到目的節(jié)點(diǎn)路由的逐跳次數(shù)被用來(lái)度量路由的優(yōu)劣。AODV協(xié)議依賴網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都擁有并維護(hù)自身的目的序列號(hào)來(lái)避免到該節(jié)點(diǎn)的所有路由出現(xiàn)環(huán)路。節(jié)點(diǎn)每當(dāng)接收到目的節(jié)點(diǎn)新的信息時(shí)，立即增加它自身的序列號(hào)。

在AODV路由中按需路由協(xié)議的路由查找、路由回復(fù)、路由錯(cuò)誤和數(shù)據(jù)轉(zhuǎn)發(fā)都得以實(shí)現(xiàn)，而AODV和其他的按需路由協(xié)議(如DSR、LAR路由協(xié)議)一個(gè)主要的改進(jìn)是加入了路由表，盡管路由表有一個(gè)生存時(shí)間，一旦時(shí)間到了就被刪除，但是AODV路由協(xié)議還是被稱為是把按需路由和表路由結(jié)合起來(lái)的一種新型路由算法[7]。AODV協(xié)議路由建立過程，如圖1所示。

圖1 AODV路由算法簡(jiǎn)介

(1)假設(shè)節(jié)點(diǎn)N8有數(shù)據(jù)要發(fā)往目標(biāo)節(jié)點(diǎn)N0，首先源節(jié)點(diǎn)檢查路由表，如果沒有找到目的節(jié)點(diǎn)或路由表已過期，源節(jié)點(diǎn)將廣播一個(gè)路由請(qǐng)求消息RREQ，RREQ報(bào)文里攜帶以下信息字段:源地址、源序列號(hào)、廣播ID、目的地址、目的序列號(hào)和路由損耗等。

(2)中間節(jié)點(diǎn)(N3、N6和 N7等)收到 RREQ后，首先查找路由表中是否有到目的節(jié)點(diǎn)的路由，如果有到達(dá)目的節(jié)點(diǎn)的路由，則回復(fù)路由響應(yīng)RREP;反之，判斷其目的地址是否是本節(jié)點(diǎn)地址，如果不是，繼續(xù)向它們周圍的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)該路由請(qǐng)求RREQ。同時(shí)中間節(jié)點(diǎn)也會(huì)記住這個(gè)路由信息，包括源節(jié)點(diǎn)、目的節(jié)點(diǎn)、上一跳地址和路由損耗等。

(3)經(jīng)過多跳廣播后，目標(biāo)節(jié)點(diǎn)N0收到這個(gè)RREQ報(bào)文，同樣，判斷其目的地址是否是本節(jié)點(diǎn)，如果是，則回復(fù)路由響應(yīng)RREP報(bào)文，RREP沿反向路由到達(dá)源節(jié)點(diǎn)N8，并建立前向路由。

源節(jié)點(diǎn)通過廣播一個(gè)路由請(qǐng)求分組發(fā)現(xiàn)了一條通往目標(biāo)節(jié)點(diǎn)的路徑，然后把要傳輸?shù)臄?shù)據(jù)沿著找到的路徑傳送出去，中間節(jié)點(diǎn)也會(huì)動(dòng)態(tài)地維護(hù)該路徑，以便正確轉(zhuǎn)發(fā)數(shù)據(jù)。源節(jié)點(diǎn)N8到目的節(jié)點(diǎn)N0有多條路徑，但AODV是基于最小跳數(shù)的，所以路由選擇N8-N3-N1-N0。

雖然AODV協(xié)議有較好的性能表現(xiàn)，但也存在一些問題:在路由發(fā)現(xiàn)過程中，AODV使用洪泛機(jī)制實(shí)現(xiàn)，而在大規(guī)模的WSNs中若直接使用AODV協(xié)議會(huì)造成很大的網(wǎng)絡(luò)開銷，并且在實(shí)際應(yīng)用中發(fā)現(xiàn)RREQ報(bào)文的沖突幾率也很高。

在ZigBee網(wǎng)絡(luò)建立之初，有節(jié)點(diǎn)會(huì)率先成為簇頭，以該簇頭為中心，其他節(jié)點(diǎn)由自組網(wǎng)算法關(guān)聯(lián)組成一棵邏輯樹。其局部網(wǎng)絡(luò)結(jié)構(gòu)，如圖2所示。這時(shí)，如果節(jié)點(diǎn)N4需要簇頭節(jié)點(diǎn)N0的路由，節(jié)點(diǎn)N4首先會(huì)向其周圍廣播RREQ報(bào)文。因?yàn)锳ODV使用洪泛機(jī)制，因此節(jié)點(diǎn)N6、N7、N8等節(jié)點(diǎn)在接收到RREQ報(bào)文后會(huì)向其周圍繼續(xù)廣播該報(bào)文，直到達(dá)到路由損耗的上限。但顯然節(jié)點(diǎn)N6、N7、N8等節(jié)點(diǎn)并不需要參與路由的發(fā)現(xiàn)過程。由于WSNs中節(jié)點(diǎn)的能量十分有限，且節(jié)點(diǎn)大部分能耗來(lái)自于無(wú)線通信消耗，因此如何在建立路由的過程中減少通信開銷成為路由協(xié)議設(shè)計(jì)的重要目標(biāo)。并且一般情況下發(fā)送數(shù)據(jù)所消耗的能量與發(fā)送距離的平方成正比[8]，因此在基于最小跳數(shù)的路由選擇中，也要考慮距離因素。針對(duì)這些問題，本文在AODV路由協(xié)議基礎(chǔ)上進(jìn)行了一些改進(jìn)。

圖2 WSNs局部邏輯結(jié)構(gòu)

2 AODV路由協(xié)議改進(jìn)方案

2.1 ZigBee組網(wǎng)技術(shù)

ZigBee網(wǎng)絡(luò)建立之初，當(dāng)前未加入任何網(wǎng)絡(luò)的節(jié)點(diǎn)會(huì)建立一個(gè)新的ZigBee網(wǎng)絡(luò)，這個(gè)發(fā)起建立網(wǎng)絡(luò)的節(jié)點(diǎn)就是該網(wǎng)絡(luò)的簇首節(jié)點(diǎn)。簇首節(jié)點(diǎn)首先進(jìn)行IEEE802.15.4中的能量探測(cè)掃描 (energy detection scan)和主動(dòng)掃描 (active scan)，選擇一個(gè)空閑信道建立網(wǎng)絡(luò)，并確定自己的16 bit網(wǎng)絡(luò)地址、網(wǎng)絡(luò)的PAN標(biāo)識(shí)符等，其中PAN ID是網(wǎng)絡(luò)在此信道中的唯一標(biāo)識(shí)。各項(xiàng)參數(shù)選定后，簇頭節(jié)點(diǎn)便可以接受其他節(jié)點(diǎn)加入該網(wǎng)絡(luò)。

當(dāng)一個(gè)未加入網(wǎng)絡(luò)的節(jié)點(diǎn)想要加入當(dāng)前網(wǎng)絡(luò)時(shí)，便向網(wǎng)絡(luò)中的節(jié)點(diǎn)發(fā)送關(guān)聯(lián)請(qǐng)求，收到關(guān)聯(lián)請(qǐng)求的節(jié)點(diǎn)如果有能力接受其他節(jié)點(diǎn)為其子節(jié)點(diǎn)，就為此節(jié)點(diǎn)分配一個(gè)網(wǎng)絡(luò)中唯一的16 bit網(wǎng)絡(luò)地址，并發(fā)出關(guān)聯(lián)應(yīng)答，收到關(guān)聯(lián)應(yīng)答后，此節(jié)點(diǎn)成功加入網(wǎng)絡(luò)，并可以接受其他節(jié)點(diǎn)的關(guān)聯(lián)。節(jié)點(diǎn)加入網(wǎng)絡(luò)后，將自己的PAN ID標(biāo)識(shí)設(shè)為與簇首節(jié)點(diǎn)相同的標(biāo)識(shí)。一個(gè)節(jié)點(diǎn)是否具有接受其他節(jié)點(diǎn)與其關(guān)聯(lián)的能力，主要取決于此節(jié)點(diǎn)可利用的資源，如存儲(chǔ)空間、能量等。

2.2 基于路徑深度的AODV路由協(xié)議優(yōu)化

ZigBee網(wǎng)絡(luò)建立之初，節(jié)點(diǎn)通過自組網(wǎng)算法關(guān)聯(lián)組成一棵邏輯樹。當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)允許一個(gè)新節(jié)點(diǎn)通過它加入網(wǎng)絡(luò)時(shí)，它們之間就形成了父子關(guān)系，每個(gè)進(jìn)入網(wǎng)絡(luò)的節(jié)點(diǎn)都會(huì)從父節(jié)點(diǎn)分配到網(wǎng)絡(luò)中唯一的16bit網(wǎng)絡(luò)地址，其地址分配算法為

式中，Cskip(d)為路徑深度為d的路由節(jié)點(diǎn)的地址空間;Cm為匯聚節(jié)點(diǎn)最大子節(jié)點(diǎn)數(shù)，取值為20;Lm為匯聚節(jié)點(diǎn)最大路徑深度，取值為10;Rm為匯聚節(jié)點(diǎn)最大路由節(jié)點(diǎn)數(shù)，取值為6。因?yàn)閷?shí)際系統(tǒng)中各個(gè)相關(guān)參數(shù)是定值，因此Cskip(d)也都是常值。

當(dāng)一個(gè)路由節(jié)點(diǎn)的Cskip(d)為0時(shí)，不再具備為子節(jié)點(diǎn)分配地址的能力;反之，則可以接受其他節(jié)點(diǎn)為它的子節(jié)點(diǎn)。它會(huì)為第一個(gè)與它關(guān)聯(lián)的路由節(jié)點(diǎn)分配比自己大1的地址，之后與之關(guān)聯(lián)的路由節(jié)點(diǎn)的地址之間都相隔偏移量Cskip(d)。假設(shè)父節(jié)點(diǎn)的地址為Aparent，則第n個(gè)與之關(guān)聯(lián)的子節(jié)點(diǎn)地址為An

由于簇頭的地址默認(rèn)采用0x0000，因此根據(jù)式(2)可得出第一代孩子節(jié)點(diǎn)的地址，即路徑深度d=1的節(jié)點(diǎn)地址為

可得出任意節(jié)點(diǎn)的地址與路徑深度d之間的關(guān)系為

因?yàn)镽REQ報(bào)文中攜帶源地址和目的地址，因此可通過式(4)計(jì)算出源地址及目標(biāo)地址的路徑深度d，并與自身路徑深度比較，路由節(jié)點(diǎn)只有在自身路徑深度在源節(jié)點(diǎn)路徑深度和目標(biāo)節(jié)點(diǎn)路徑深度范圍之內(nèi)時(shí)，才進(jìn)行RREQ報(bào)文的轉(zhuǎn)發(fā)。在圖2中，節(jié)點(diǎn)N7的路徑深度d=3，并不在源節(jié)點(diǎn)N4和目的節(jié)點(diǎn)N0的路徑深度范圍[0～2]之內(nèi)，因此節(jié)點(diǎn)N7不會(huì)參與到節(jié)點(diǎn)N4向節(jié)點(diǎn)N0的路由建立過程，減少了相應(yīng)節(jié)點(diǎn)(N6、N7和N8等)的轉(zhuǎn)發(fā)RREQ報(bào)文的通信開銷。

2.3 AODV 路由維護(hù)

路由維護(hù)是網(wǎng)絡(luò)層的一個(gè)重要的功能，在節(jié)點(diǎn)經(jīng)過路由查找找到一條合適的路徑之后，會(huì)把這條路徑保存在路由表中。由于節(jié)點(diǎn)自身資源的限制，其存儲(chǔ)器的空間有限，如果在一個(gè)區(qū)域內(nèi)布置大量的傳感器節(jié)點(diǎn)，那么其路由表所占的空間將會(huì)是一個(gè)很大的開銷。由于這個(gè)原因，節(jié)點(diǎn)的路由表不會(huì)一直存在，在建立路由表時(shí)，會(huì)啟動(dòng)一個(gè)定時(shí)器。經(jīng)過一定的時(shí)間，路由表中的某些表項(xiàng)如果不用，就會(huì)被刪除，以防止路由表不斷增大，從而節(jié)省資源。

如果源節(jié)點(diǎn)是移動(dòng)的，或者路由表中的相應(yīng)表項(xiàng)被刪除，如果有數(shù)據(jù)要發(fā)送至目的節(jié)點(diǎn)時(shí)，它就要向目的節(jié)點(diǎn)重新發(fā)起一次路由發(fā)現(xiàn)過程，建立新的路由。

2.4 基于RSSI的最短路徑選擇

節(jié)點(diǎn)硬件由LPC2138作為主控制器，由TI公司的CC2420組成的射頻模塊作為通信模塊。CC2420內(nèi)部集成了可用于實(shí)現(xiàn)節(jié)點(diǎn)測(cè)距功能的數(shù)字RSSI模塊，通信距離越遠(yuǎn)，RSSI值相對(duì)越低。CC2420支持八個(gè)不同的發(fā)送功率等級(jí)，通過大量實(shí)驗(yàn)，選擇第五功率作為節(jié)點(diǎn)通訊的發(fā)射功率。第五功率下RSSI隨距離變化的趨勢(shì)，如圖3所示。RSSI單位為dbm，距離單位為m。可以看出，采用第五功率時(shí)，在通信距離為0～15 m范圍內(nèi)RSSI逐漸減小，波動(dòng)較少。

圖3 RSSI隨距離變化趨勢(shì)圖

由于節(jié)點(diǎn)可以檢測(cè)RSSI值，如圖4所示，節(jié)點(diǎn)N5到N0的路由廣播時(shí)，路由節(jié)點(diǎn)(如節(jié)點(diǎn)N3、N4)收到RREQ報(bào)文后并不是立即轉(zhuǎn)發(fā)，而是延遲一個(gè)適當(dāng)?shù)呐c節(jié)點(diǎn)測(cè)得的RSSI值成反比的時(shí)間轉(zhuǎn)發(fā)，也就是節(jié)點(diǎn)間距離越遠(yuǎn)，延遲時(shí)間越長(zhǎng)。這樣RREQ會(huì)選擇一個(gè)較短的路徑優(yōu)先達(dá)到目的節(jié)點(diǎn)，目的節(jié)點(diǎn)收到最先到達(dá)的RREQ后回復(fù)RREP，從而建立路由，而路由回復(fù)則不進(jìn)行時(shí)間延遲。其他的路徑較長(zhǎng)的RREQ，由于到達(dá)目的節(jié)點(diǎn)時(shí)，目的節(jié)點(diǎn)已經(jīng)建立了路由，因此不會(huì)進(jìn)行路由回復(fù)。圖4中，選擇的最短路徑是N5-N3-N1-N0。基于RSSI的時(shí)間延遲，即可以通過不同的延遲時(shí)間避免節(jié)點(diǎn)間的RREQ的沖突，也可以選擇一個(gè)距離較短的路徑以減少通信消耗。

圖4 基于RSSI的RREQ報(bào)文轉(zhuǎn)發(fā)

3 協(xié)議實(shí)驗(yàn)及結(jié)果、性能分析

協(xié)議使用自主開發(fā)的節(jié)點(diǎn)平臺(tái)[9]進(jìn)行了實(shí)驗(yàn)，節(jié)點(diǎn)及節(jié)點(diǎn)分布，如圖5所示。簇頭節(jié)點(diǎn)通過串口與上位機(jī)連接，通過上位機(jī)的界面程序，監(jiān)測(cè)無(wú)線傳感器網(wǎng)絡(luò)狀態(tài)。

圖5 節(jié)點(diǎn)及節(jié)點(diǎn)分布

基于路徑深度的AODV路由協(xié)議優(yōu)化實(shí)驗(yàn)?zāi)M的結(jié)構(gòu)，如圖2所示。使節(jié)點(diǎn)N4向節(jié)點(diǎn)N0發(fā)送數(shù)據(jù)，計(jì)算機(jī)通過串口與節(jié)點(diǎn)N7連接，監(jiān)測(cè)節(jié)點(diǎn)N7的狀態(tài)。通過節(jié)點(diǎn)N7的串口輸出，可了解到節(jié)點(diǎn)N7在接收到N4發(fā)送的RREQ報(bào)文之后，通過源節(jié)點(diǎn)與目的節(jié)點(diǎn)路徑深度計(jì)算，沒有繼續(xù)向周圍轉(zhuǎn)發(fā)RREQ報(bào)文，收到的消息量也明顯減少。而在相同結(jié)構(gòu)下的原AODV路由協(xié)議中，節(jié)點(diǎn)N7則會(huì)把RREQ報(bào)文轉(zhuǎn)發(fā)出去。因?yàn)槠渌?jié)點(diǎn)(節(jié)點(diǎn)N6、N8等)也會(huì)進(jìn)行相同的操作，因此節(jié)點(diǎn)N7會(huì)收到很多相同的RREQ。在節(jié)點(diǎn)規(guī)模達(dá)到20個(gè)以上時(shí)，也會(huì)出現(xiàn)報(bào)文沖突現(xiàn)象。

基于RSSI的最短路徑選擇實(shí)驗(yàn)，如圖6所示，圓點(diǎn)之間的虛線表示節(jié)點(diǎn)間的邏輯關(guān)系。節(jié)點(diǎn)間的距離在4～5 m之間。從圖6中可看出基于RSSI的路徑選擇會(huì)優(yōu)先選擇最短路徑，節(jié)點(diǎn)5的組網(wǎng)數(shù)據(jù)通過路徑5-4-2-0發(fā)送到簇頭節(jié)點(diǎn)，而原AODV路由協(xié)議的路徑選擇，隨機(jī)性比較大。

圖6 上位機(jī)演示圖

4 結(jié)語(yǔ)

在AODV路由協(xié)議基礎(chǔ)上，考慮了節(jié)點(diǎn)的路徑深度及路由選擇的距離因素。在中間節(jié)點(diǎn)收到RREQ報(bào)文時(shí)，使不在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的節(jié)點(diǎn)停止路由轉(zhuǎn)發(fā)，減少了參與路由發(fā)現(xiàn)過程的節(jié)點(diǎn)數(shù)，以此減少了WSNs的能耗。在轉(zhuǎn)發(fā)RREQ報(bào)文時(shí)延遲了一個(gè)與測(cè)得的RSSI成反比的時(shí)間，減少了RREQ報(bào)文的沖突，并最大可能地選擇距離短的路徑作為傳輸路徑，減少了無(wú)線通信消耗。對(duì)于實(shí)時(shí)性要求不高的網(wǎng)絡(luò)，有很好的應(yīng)用價(jià)值。實(shí)驗(yàn)表明，經(jīng)過改進(jìn)的路由協(xié)議具有更優(yōu)的性能，明顯減少了通信量。

[1]AKYILDIZ IF，SU WEI-LIAN，SANKARASUBRAMANIAM Y，et al.A Survey on Sensor Networks[J].IEEE Communications Magazine，2002，40(8):102-114.

[2]任雄偉.無(wú)線移動(dòng)自組網(wǎng)中路由度量和路由策略的研究[D].武漢:華中科技大學(xué)，2005.

[3]YOUNIS O，F(xiàn)AHMY S.A Hybrid，Energy-Efficient，Distributed Clustering Approach for Ad-Hoc Sensor Networks[J].IEEE Transaction on Mobile Computing，2004，3(4):660-669.

[4]李慶，劉聰，江漢紅，等.Ad Hoc網(wǎng)絡(luò)中AODV路由協(xié)議的優(yōu)化[J].計(jì)算機(jī)工程.2008，34(13):107-109.

[5]吳麗杰，錢雪忠，竇維江.基于AODV的能量有效路由協(xié)議[J].微電子學(xué)與計(jì)算機(jī).2006，23(10):219-221.

[6]PERK NS C E，ROYER E，DAS S.RFC 3561，Ad Hoc On-Demand Distance Vector(AODV)Routing[S].2003.

[7]鄭少仁，王海濤，趙志峰，等.Ad Hoc網(wǎng)絡(luò)技術(shù)[M].北京:人民郵電出版社，2005.

[8]HEINZELMAN W R，CHANDRAKASAN A，Balakrishnan H.An Application-Specific Protocol Architecture for Wire-less Microsensor Networks[J].IEEE Trans.on Wireless Communications，2002，1(4):660-670.

[9]高英明，金仁成，王宏斌，等.基于ARM7的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量管理初探[J].微納電子技術(shù)，2007(8):450-452.