??? 摘 要： 針對低速無線個域網(wǎng)" title="低速無線個域網(wǎng)">低速無線個域網(wǎng)的特點，在AODV基礎(chǔ)上設(shè)計并實現(xiàn)了一種考慮節(jié)能、對硬件資源要求低、收斂速度快的路由協(xié)議" title="路由協(xié)議">路由協(xié)議，該協(xié)議包含“反饋控制" title="反饋控制">反饋控制標志”、“上游節(jié)點尋路”、“只限廣播的擴展環(huán)搜索”等優(yōu)化策略。進一步給出路由協(xié)議模型、報文格式以及算法實現(xiàn)流程，與同類協(xié)議進行了性能比較。實驗結(jié)果表明，協(xié)議在存儲資源消耗、鏈路" title="鏈路">鏈路修復(fù)、帶寬占用等方面具有很強的優(yōu)勢。
??? 關(guān)鍵詞： 低速無線個域網(wǎng)； 路由協(xié)議； AODV
?
??? 低速無線個域網(wǎng)（LR-WPAN）是指在個人操作空間POS（Personal Operation Space）內(nèi)低速率、低功耗、低成本的設(shè)備之間建立無線通信實現(xiàn)各種信息交互的一種區(qū)域性聯(lián)網(wǎng)技術(shù)，具有易于安裝、可靠傳輸、短距離通信、極低功耗、協(xié)議簡單靈活等特點，可以廣泛用于智能家居、遠程醫(yī)療和工業(yè)控制等領(lǐng)域。
??? 目前，LR-WPAN路由協(xié)議沒有統(tǒng)一標準，各LR-WPAN商業(yè)和研究組織采用不同的路由協(xié)議。這些協(xié)議大多是AODV[1]的簡化和改進版本，參考文獻[2-6]對基于AODV的各種協(xié)議做了詳盡的介紹和比較，從中總結(jié)常見的簡化措施有：
??? （1）不使用目的節(jié)點序列號，同時規(guī)定只有分組的目的節(jié)點可以回復(fù)RREP（路由應(yīng)答）以避免環(huán)路問題。
??? （2）取消前向節(jié)點列表。傳播鏈路失效消息的方式改為向上游廣播或向源節(jié)點單播RERR（路由錯誤包），有的協(xié)議甚至取消RERR，完全依靠本地鏈路修復(fù)重建路由。
??? （3）不采用IP包作為載體。路由協(xié)議直接實現(xiàn)在2.5層，對上層協(xié)議透明。
??? 本文所提出的路由協(xié)議采用了這些簡化措施，同時創(chuàng)新性地提出了“反饋控制標志”、“上游節(jié)點尋路”、“只限廣播的擴展環(huán)搜索”等技術(shù)，具有低資源消耗、低帶寬占用、收斂速度快等優(yōu)點，能夠滿足低速無線個域網(wǎng)的需求。
1 基于AODV的路由設(shè)計方案
1.1 LWRP的提出
??? AODV的各種改進協(xié)議適用于低速無線個域網(wǎng)，但大部分協(xié)議還存在以下問題：
??? （1）對節(jié)能考慮不周。例如AODVjr只選最快的路由，沒有把鏈路質(zhì)量、節(jié)點能量考慮在內(nèi)。
??? （2）路由表" title="路由表">路由表占用存儲資源過多。例如LOAD需要建立端對端的雙向通信，中間節(jié)點需要有到兩個通信對端的雙向路由，在網(wǎng)絡(luò)規(guī)模較大的情況下路由表對存儲資源的占用很大。
??? （3）對廣播風暴抑制不夠。在一些監(jiān)測控制應(yīng)用中，LR-WPAN節(jié)點相對密集，廣播包數(shù)量過多會引起通信信道的阻塞。
??? 針對以上問題，提出了更適合低速無線個域網(wǎng)的路由協(xié)議LWRP（LR-WPAN Routing Protocol)。本協(xié)議具有以下特點：
??? （1）在路由請求報文中設(shè)置“弱鏈路條數(shù)”、“能量告警節(jié)點個數(shù)”等字段。優(yōu)選路由時，綜合考慮跳數(shù)、鏈路質(zhì)量、節(jié)點能量情況，而且將節(jié)點能量作為選路最重要的指標，能夠滿足LR-WPAN對節(jié)能的需求。
??? （2）反饋控制標志。在路由請求和路由回復(fù)報文中設(shè)置“反饋控制標志”字段，能夠根據(jù)節(jié)點本身的特點決定是否建立反向路由，在不影響網(wǎng)絡(luò)功能的前提下大大減少路由表的條數(shù)，從而減少對存儲資源的占用。
??? 此設(shè)計基于以下考慮：LR-WPAN一般用于檢測控制，數(shù)據(jù)流具有多對一單向通信特點，網(wǎng)絡(luò)中大部分節(jié)點只關(guān)心去往Sink節(jié)點的路由，在無需反饋控制的路徑上只需建立到Sink的正向路由，因此路由表可以極為精簡。
??? （3）只限廣播的擴展環(huán)搜索。在路由請求報文中設(shè)置“廣播跳數(shù)限制”字段，對報文傳輸范圍進行靈活控制，能夠在限制廣播包擴散范圍的情況下保證建立路由的成功率。
??? 圖1是廣播包跳數(shù)限制示意圖，其中D、E沒有到Sink的路由。 C請求到Sink路由，其路由請求包中“廣播包跳數(shù)限制”字段為1，那么D收到此包后不會再廣播該請求，E點不會受到干擾。而A點有到Sink路由，會繼續(xù)單播該請求，最后C與Sink之間通過A、B兩跳成功建立路由。
?
??? 設(shè)計思想來源：AODV提出“擴展環(huán)搜索”技術(shù)，以避免路由請求包整網(wǎng)擴散。需要注意的是，AODV允許中間節(jié)點回復(fù)路由請求，即中間節(jié)點有到目的節(jié)點路由時會回復(fù)RREP，而LR-WPAN使用的各種AODV簡化協(xié)議，由于沒有采用序列號機制，均規(guī)定只有目地節(jié)點可以回復(fù)路由，如果依然采用AODV中“擴展環(huán)搜索”策略，將存在以下問題：當發(fā)起RREQ的節(jié)點與目的節(jié)點相距較遠時，即使中間節(jié)點有到達目的地的路由，也不能回復(fù)RREP，這樣需要多次搜索，對網(wǎng)絡(luò)帶寬占用造成很大壓力，可能得不償失。
??? (4)上游節(jié)點參與本地鏈路修復(fù)，增加了路由修復(fù)成功率，提高了網(wǎng)絡(luò)自愈能力。
??? 修復(fù)算法描述如下
??? 收到路由修復(fù)RREQ；
???? IF有到RREQ目的節(jié)點的路由 THEN
?????? IF 此路由下一跳是RREQ源節(jié)點 THEN
????????? 刪除此路由表項；
????? IF ?廣播包限制字段非零 THEN
??????????? ????? 廣播RREQ；
????? ELSE
????????????? ??? 丟棄RREQ包；
???????? ???? END IF
????? ELSE
????????? ??????? 單播RREQ到下一跳；
??????????? END IF
???? ELSE
???? IF ?廣播包限制字段非零 THEN
???????? ??? 廣播RREQ；
???? ELSE
???????? 丟棄RREQ包；
?????????END IF
??? END IF
??? 上游節(jié)點參與路由如圖2所示，其中，A節(jié)點轉(zhuǎn)發(fā)目的為Sink的數(shù)據(jù)包時沒有得到下一跳節(jié)點B的確認（B節(jié)點死亡），廣播源為A目的為Sink的路由請求。A的上游鄰居D 收到該RREQ之后，判斷出自己到Sink的路由下一跳為A，于是刪除到Sink路由并繼續(xù)廣播該RREQ報文，最后A到Sink通過D、C建立路由。
?
1.2? 路由協(xié)議模型
??? IEEE 802.15.4[7,8]是低速無線個域網(wǎng)媒體訪問控制層和物理層標準，LWRP運行在這一標準之上并直接使用IEEE 802.15.4規(guī)定的EUI-64 地址作為路由依據(jù)。為了在IEEE 802.15.4上同時運行LWRP和TCP/IP等協(xié)議，需要一個中間適配層。LWRP協(xié)議所處層次如圖3所示。
?
1.3? 報文格式
??? LWRP規(guī)定兩種報文RREQ、RREP幀格式分別見圖4(a)、(b)。
?
??? 字段說明如下：
??? （1）類型：0x00表示RREQ報文；0x01表示RREP報文。
??? （2）反饋控制標志：值為１表示RREQ源和目地需要雙向通信，否則為單向通信。
??? （3）弱鏈路條數(shù)：從RREQ源節(jié)點到當前節(jié)點經(jīng)過的鏈路質(zhì)量低于規(guī)定標準的鏈路條數(shù)。
??? （4）能量告警節(jié)點個數(shù)：從RREQ源節(jié)點到當前節(jié)點經(jīng)過的電量不足的節(jié)點個數(shù)。
??? （5）跳數(shù)：報文從出發(fā)點到當前節(jié)點經(jīng)過的跳數(shù)。
??? （6）廣播跳數(shù)限制：RREQ廣播范圍限制。
??? （7）路由請求ID：與源節(jié)點一起，唯一標識一個RREQ消息。
??? （8）源地址：RREQ源節(jié)點的IEEE802.15.4定義的64bit接口標識符。
??? （9）目的地址：RREQ目的地址的IEEE802.15.4定義的64bit接口標識符。
2 路由算法的實現(xiàn)
??? LWRP是按需驅(qū)動路由協(xié)議，節(jié)點不需要維護及時準確的路由信息，當向目的節(jié)點發(fā)送報文時，源節(jié)點才在網(wǎng)絡(luò)中發(fā)起路由查找過程，協(xié)議開銷小，符合低速無線個域網(wǎng)節(jié)能要求。
2.1 路由建立過程
??? （1）發(fā)送RREQ
??? 當某節(jié)點發(fā)送數(shù)據(jù)到其他節(jié)點時，首先查找本地路由表，如果發(fā)現(xiàn)到目的地址的路由不存在，則緩存當前數(shù)據(jù)包，封裝RREQ報文，廣播發(fā)送RREQ消息。
??? （2）中間節(jié)點接收到RREQ
??? 如圖5所示，接收RREQ報文的節(jié)點首先判斷RREQ報文目的地址是否是自己，如果不是，則查詢自己的入口表。
?
??? 如果已經(jīng)存在入口表項，表明已經(jīng)接收過與該RREQ源地址發(fā)送ID號相同的RREQ報文。為防止廣播風暴，該節(jié)點拋棄RREQ報文。
??? 如果不存在該入口表項，則在路由表中查詢能夠到達RREQ源地址的路由。如果已經(jīng)存在該路由，則比較這兩條路由，選擇較好的路由進行存儲；如果不存在該路由，則臨時建立一條到RREQ源地址的逆向路由。然后，節(jié)點查詢路由表中到RREQ報文中目的地址的路由，如果存在，則向目的節(jié)點單播RREQ消息，否則繼續(xù)廣播RREQ報文。
??? （3）目的節(jié)點接收RREQ和發(fā)送RREP
??? RREQ的目的節(jié)點首先緩存RREQ報文消息，由于廣播RREQ尋路過程，節(jié)點接收多條路由到達的報文消息，所以需要等待合理時間T，進行多路由的優(yōu)劣判斷。協(xié)議構(gòu)造路由優(yōu)選函數(shù)f(m,h,n)：
??? ?f(m,h,n)=Am+Bh+Cn
其中,m為源節(jié)點到目的節(jié)點經(jīng)過的電量不足節(jié)點的個數(shù)，ｈ為源節(jié)點到目的節(jié)點的跳數(shù)，ｎ為從源節(jié)點到目的節(jié)點弱鏈路的條數(shù)。考慮到節(jié)能是其中最主要的因素，結(jié)合實際測量情況，在開闊地帶室外環(huán)境下，可取A= 256，B=1，C=2。目的節(jié)點為每個到達的RREQ計算其f值，選擇f值最小的路由進行回復(fù)。
??? （4）接收RREP
??? 接收RREP的過程如圖6所示。當節(jié)點接收到RREP報文，首先建立到RREP源地址的路由表項，然后判斷RREP目的地址是不是自己。如果是，則發(fā)送緩存隊列中的緩存數(shù)據(jù)；如果不是，則建立或者更新到RREP源地址的路由表項，并找出到RREP目的地址的路由，判斷RREP中的反饋控制位是否為1，是則將此路由修改為正式路由，繼續(xù)單播RREP報文。
?
2.2? 路由維護過程
??? 節(jié)點向鄰居節(jié)點發(fā)送數(shù)據(jù)后，在一定時間內(nèi)沒有收到確認幀，則認為該鄰居節(jié)點失效。此時，節(jié)點緩存當前數(shù)據(jù)，并發(fā)起本地修復(fù)過程，廣播RREQ尋找到該數(shù)據(jù)目的節(jié)點的路由。
??? 節(jié)點本地修復(fù)RREQ的“廣播跳數(shù)限制”取值比較小，一般小于3，以避免RREQ報文引起網(wǎng)絡(luò)中廣播風暴。廣播跳數(shù)限制不會影響單播RREQ所能到達的網(wǎng)絡(luò)范圍，因此這種設(shè)計既能避免廣播包擴散又能很好地修復(fù)路由。
3? LWRP的性能分析
??? 實驗網(wǎng)絡(luò)采用圖7所示拓撲，其中只有C需要反饋控制，各節(jié)點只與周圍鄰居通信。圖中括號內(nèi)數(shù)字是節(jié)點EUI-64地址最后一個字節(jié)的十六進制表示值。讓節(jié)點發(fā)送包含自己內(nèi)部路由表情況的數(shù)據(jù)包，通過Chipcon Packet Sniffer[9]抓包并進行分析。
?
??? （1）對存儲和計算資源的占用
??? 圖8對比了運行LWRP和LOAD協(xié)議后各節(jié)點路由表項數(shù)目。
?
??? 假設(shè)網(wǎng)絡(luò)規(guī)模為n，Sink單跳范圍內(nèi)節(jié)點個數(shù)為m，反饋控制節(jié)點占總節(jié)點數(shù)比例k%，每條路由表占用存儲資源為s。由于Sink周圍節(jié)點路由表條數(shù)比其他節(jié)點多，用Sink單跳范圍內(nèi)節(jié)點路由表占用內(nèi)存的平均值來衡量協(xié)議對存儲資源的要求。
??? 運行LOAD后該平均值為：
??? ?s*[1+(n-m-1)/m]
??? 而運行LWRP后，該值為:
??? ?s*[1+nk%/m]
??? 在一般數(shù)據(jù)采集應(yīng)用中，n>>m，而k%很小，LWRP路由表占用存儲資源優(yōu)勢很明顯。
??? 計算資源方面，LWRP只進行簡單比較和線性查找運算，其優(yōu)選函數(shù)以2的非負指數(shù)次方作為加權(quán)系數(shù)，能夠利用MCU的移位運算快速得到結(jié)果。
??? （2）自愈性
??? 圖7顯示拓撲條件下，F(xiàn)點向Sink發(fā)送數(shù)據(jù)。某時刻將B節(jié)點斷電模擬實際環(huán)境中節(jié)點死亡，從實驗結(jié)果觀察G點流量。結(jié)果顯示A點檢測到AB之間鏈路斷開，緩存了來自F的數(shù)據(jù)包，開始本地修復(fù)過程。
??? 運行LOAD協(xié)議時，A節(jié)點的本地修復(fù)失敗，造成數(shù)據(jù)包丟失。而運行LWRP時，上游節(jié)點D參與尋找路由過程，將來自A的RREQ又廣播了一次，成功完成本地修復(fù)過程，緩存的數(shù)據(jù)包通過A->D->G->Sink到達目的地。
??? （3）網(wǎng)絡(luò)帶寬占用
??? 在更大規(guī)模網(wǎng)絡(luò)中通過將節(jié)點斷電模擬實際環(huán)境中節(jié)點失效，抓包分析不同路由協(xié)議廣播包數(shù)量得出結(jié)論，相比AODVjr和LOAD，LWRP能夠有效控制RREQ廣播包數(shù)量，網(wǎng)絡(luò)規(guī)模越大，優(yōu)勢越明顯。
??? 表1給出了LWRP和其他基于AODV的同類路由協(xié)議的對比。
?
??? LWRP已經(jīng)在實際生產(chǎn)中長期穩(wěn)定運行，協(xié)議在硬件資源占用、節(jié)能、無線帶寬控制、網(wǎng)絡(luò)自愈性等方面體現(xiàn)出優(yōu)越性。下一個目標是解決Sink周圍數(shù)據(jù)流密集可能造成的擁塞，將負載均衡作為路由設(shè)計中一項因素加以考慮。
參考文獻
[1]? RFC3561, PERKINS C. Ad hoc On-Demand Distance Vector(AODV) Routing [S].2003.
[2] ?GOMEZ C. Adapting AODV for IEEE 802.15.4 mesh sensor networks: Theoretical discussion and performance evaluation in a real environment. Proceedings of the 2006 International Symposium on a World of Wireless, Mobile and Multimedia Networks,2006.
[3] ?ZigBee document 053474r07. Version 1.1,ZigBee Specification[S], 2005.
[4] ?CHAKERES I, Klein-Berndt L. AODVjr, AODV Simplified[J]. Mobile Computing and Communications Review,2002,6(3):100-101.
[5] ?6LowPan document．http://www.ietf.org
[6] ?IETF Internet Draft, 6LoWPAN Ad Hoc On-Demand Distance Vector Routing (LOAD) [S].2006.
[7] ?孫利民,李建中，陳渝，等. 無線傳感器網(wǎng)絡(luò)[M]. 北京：清華大學(xué)出版社，2005.
[8] ?IEEE Std 802.15.4. IEEE standard for wireless Medium Access Control(MAC) and Physical Layer(PHY) specifications for Low-Rate Wireless Personal Area Networks (LR-WPANs)[S]. 2003.
[9] ?Chipcon Sniffer User Manual. http://www.chipcon.com.