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