基于LBS及網絡編碼的HWMP路由協議

龍昭華，秦曉煥，劉達明，2

（1.重慶郵電大學 計算機科學與技術學院，重慶400065；2.重慶郵電大學 移通學院，重慶401520）

0 引 言

無線Mesh網絡的標準化研究推動著無線Mesh技術的發展，IEEE 802.11s標 準 正 是 在 這 種 推 動 下 建 立 的［1，2］。HWMP［3］是IEEE 802.11s標準的默認路由協議。HWMP協議將按需路由和先驗式路由有機的結合在了一起，同時兼顧了按需路由的靈活性及反應式路由的快速性，為網絡中路由的查找提供了較好的方法。HWMP只適用于節點通信較少的網絡中，如果無線網絡中有很多節點要和外面的有線網絡中節點進行通信，就會產生大量的數據流，此時就會造成根節點的擁塞。

為更好滿足無線Mesh 網絡路由協議快速、準確、高效、可擴展性的目標，本文在原來HWMP 協議生成先驗式生成樹的過程中加入節點信息本地鏈接庫 （local association base，LBS），一定程度上減少了根節點的負擔；在生成樹建立以后，根據節點通信過程中數據流的特點，在原來協議的基礎上加入了網絡編碼算法。仿真結果表明，加入編碼算法后網絡吞吐量在網絡通信量增加時大大增加。

1 HWMP協議中存在的問題

HWMP協議中主要存在的問題是在無線Mesh網絡的混合路由模式中 （按需路由＋到根節點的樹），如果源節點沒有到目的節點的路徑，將把數據先發送到根節點。如果目的節點在Mesh網絡中，根節點將數據轉發到目的節點，從而建立從源節點到根節點再到目的節點的路徑。這種方式雖然能使網內2個節點立即開始通信，但也存在一定缺陷：網絡中的2個節點即使有最優的路徑也得通過根節點進行數據的轉發，根節點將成為網絡中通信的瓶頸，同時非最優化路徑的選擇也將會造成時延［4］。在目前的無線Mesh網絡的網絡架構中，因為大部分Mesh節點都是固定的，所以網絡拓撲也相對穩定。當HWMP 中基于先驗式的生成樹建立后，網絡中就會存在多個核心節點，當網絡中的通信流量很大時，就容易在這些節點處擁塞，網絡編碼則增加了轉發數據時對數據包的處理能力，通過對收到的數據包進行一定的線性或者非線性編碼，然后再轉發出去，從而提高整個網絡的吞吐量、均衡網絡負載、降低能量消耗。在這些核心節點上將會有多個數據流通過，這就給核心節點進行流間編碼創造了機會。

2 基于LBS的HWMP協議改進

2.1 現有的路由協議介紹

在HWMP協議的先驗式生成樹路由模式中，如果源節點沒有到目的節點的路徑，源節點不會發起路徑查找而是將數據直接發給父節點。父節點收到數據包后會首先查看目的地址是否是自己的子節點，如果是則轉發數據，如果不是則繼續向上層父節點轉發。當根節點MPP［5］收到數據包后會查看目的地址是否在Mesh網內部，如果是則通過先驗樹轉發至內網，否則轉發到外部網絡。這種通信方式適合于網絡中的數據大部分是與Mesh外網交互。然而當網絡內部節點通信時，將會因為通信節點之間路徑不是最優，且數據通信大部分集中于根節點，從而導致網絡性能的降低。圖1為Mesh網絡內部節點通信時的情形。假設根節點MPP為1，源節點為4，目的節點為6，按照先驗式生成樹建立起來的節點4和節點6之間的路徑為4—2—1—3—6，這時即使兩節點間存在最優路徑4—5—6，數據仍然是按4—2—1—3—6進行轉發［6］，從而造成數據的時延和網絡吞吐量的降低。

圖1 無線Mesh網內部節點通信

2.2 改進的路由協議

HWMP先驗式生成樹路由模式在Mesh 網絡節點與外部網的通信情境中有很大的優勢；而按需路由模式則在Mesh網絡內部節點的通信中占優勢。因此，需要把兩種模式的優點結合起來找到適合上述兩種通信方式的最佳路徑。

在先驗式生成樹模式中，網絡生成樹建立后，根節點MPP中有到網絡中每個節點的路徑信息，我們可以以此為基礎建立簡單的節點信息本地鏈接庫LBS，網絡中節點獲知這些信息后就可以以這些信息來判定目的節點是否在Mesh網絡內部，從而決定是否采用按需路由來獲得最佳路徑。LBS是一個hash表，表中內容為以網絡中節點MAC地 址 為key 的hash 值［7］。通 過 對RANN 幀 的 擴 展 加 入LBS，可以將這些信息發送到網絡中的每個節點。新的RANN 控制幀如圖2所示。其中changed 字段B0位標示根節點MPP本地LBS信息是否改變，如為1則表明LBS信息改變，0則表示未改變，此時LBS 中只包含changed及CRC信息，changed B0位默認值為1。CRC 為hashID 的校驗碼，hashID 是根節點根據網絡內節點MAC 值生成的hash值。根節點MPP產生RANN 消息及網絡中節點收到RANN 消息處理過程如下：

（1）根節點MPP 生成RANN 消息：先驗式生成樹建立時，根節點將根據網絡中節點的MAC地址建立hash表，以hash表中的hash值為基礎建立LBS信息庫。將LBS及其CRC加入RANN 中廣播到Mesh網絡中。如果本地LBS未改變將只在RANN 中加入LBS的CRC值。

（2）Mesh節點收到RANN 消息：網絡中的Mesh節點收到RANN 時首先查看RANN 中的Changed B0位，當B0位為0，如果CRC與本地LBS的CRC值相同則忽略，否則將向根節點MP 發送請求LBS 的RLBS 幀；當B0 位為1時，將提取LBS更新節點本地的LBS庫。

為了同步Mesh節點和根節點MP的LBS信息，Mesh節點可以向根節點MPP發送RLBS （Request LBS）幀，主動請求LBS信息。RLBS幀的幀格式如圖3所示。

改進的Mesh 網內節點間路徑選擇算法偽代碼如圖4所示。

在新的路徑選擇算法中，如果Mesh 網內源節點需要向目的節點發送數據，若到目的節點的路徑不在本地路由表中，源節點首先以目的節點MAC 為key，通過hash 函數得出相應的hashID 值，如果該值不存在本地LBS信息庫中，源節點將把數據發給根節點MPP。否則源節點將把數據發給父節點，通過中間節點直接通信，同時源節點發出PREQ 消息開始新的路徑發現過程。當源節點收到目的節點返回的RREP消息后，如果得到的新路徑優于現有的路徑，將使用新路徑建立起與目的節點通信。通過這種新的路徑選擇算法，即保留了原有路徑選擇的優勢，同時又可使網內節點間通信時可以找到最優的通信路徑，降低了根節點轉發數據的壓力。

圖2 HWMP RANN 控制幀格式及LBS字段

圖3 HWMP RLBS幀格式

圖4 改進的HWMP路徑選擇算法

3 HWMP協議中的機會主義網絡編碼

在無線Mesh網絡的網絡架構中，因為Mesh節點大部分都是固定的，所以網絡拓撲也相對穩定［8，10］。當HWMP中基于先驗式的生成樹建立后，網絡中就會存在多個核心節點，在這些核心節點上將會有多個數據流通過，這就給核心節點進行流間編碼創造了機會。

圖5是無線Mesh網絡先驗式生成樹的一部分，核心節點為R，在COPE［9］中是采用鄰節點間不斷的交換接收報告來確定編碼機會的，這需要浪費很大的帶寬，而一旦接收報告丟失或者延遲也將導致無法進行最優編碼。但在無線Mesh網絡中，對于經過核心節點的數據流，如果知道兩條數據流的下一跳節點是鄰節點，就可以判斷兩個節點間可以互相偵聽到對方發送的數據包，核心節點也就可以據此對這兩條數據流數據包進行編碼。從而省去了不斷傳輸鄰節點間接收報告。以圖5為例，數據流f1，f2都經過核心節點R，通過獲知鄰節點A、B、D、E 的鄰節點信息可知流f1和流f2的下一跳節點之間互為鄰節點，這也就意味著A、B，D、E兩對節點都分別可以偵聽到對方發出的數據包。R 將A 發給D，E發給B 的數據包異或編碼后隨機選定D 為目的節點發出去，B、D 在收到編碼數據包后根據收到的鄰節點數據均可以正確解碼，提取出自己所需要的數據。具體編碼算法及流程將在下面進行分析。

圖5 基于HWMP協議流間編碼示例

3.1 HWMP協議流間網絡編碼算法

流間無線網絡編碼是在HWMP 協議先驗式生成樹的基礎上，利用到根節點的生成樹的路由表項來探測每個節點的編碼機會，對于有編碼機會的核心節點如果滿足條件，就對經過核心節點的數據流進行編碼，從而提高網絡的吞吐量。流間網絡編碼主要用于無線Mesh網絡基礎網絡架構，只要編碼的節點所存儲的與編碼多個數據流相關的路由表項沒變化，且編碼節點與鄰節點的拓撲鏈接狀況良好，就可以對滿足條件的數據流進行持續的相似編碼操作，而不像現有的面向數據包的算法一樣對每個數據包都要進行編碼條件判斷［11］。

3.2 編碼算法

流間網絡編碼是在HWMP 先驗式生成樹的基礎上，充分利用網絡中節點所維護的路由表項來探測編碼的機會。具體的算法流程如下：

（1）數據傳輸初始階段：假設網絡中存在n個獨立的數據流f1，f2，...，fn，則n個數據流在HWMP 協議中采用先驗式或者按需式的方式選定各自的路由。每一條數據流有源節點Srci和目的節點Dsti來唯一的確定。在流fi路徑上的每個中間節點R 的路由表項包含以下信息：到達Dsti的下一跳節點NH（Dsti） （fi流經節點R 時的下一跳），到達Srci的下一跳節點PreHop（Srci）（fi流經節點R 時的上一跳節點，用于建立反向路徑）。

（2）在未使用編碼時，數據流f1，f2，...，fn分別沿著各自的路徑傳輸數據。當引入無線網絡編碼的機制后，網絡中存在多個數據流的節點 （即核心節點）在通信的過程中對流經當前節點的數據流路由表項進行檢查，如果滿足編碼條件，就啟動編碼進程，否則只對數據包進行簡單的存儲轉發。

假設網絡中存在一個核心節點R，數據流fi，fj流經R，此時R 通過編碼判定就可以決定是否可以對流fi數據包pifj數據包pj進行編碼操作。

具體的編碼算法偽代碼如圖6所示。

圖6 流間網絡編碼算法

當節點R 發現fi，fj流經時，首先會探測編碼的機會，如果fi流經R 時的下一跳節點NH（pi）為fj流經R時的上一跳節點PreH（pj）的鄰節點，且如果fj流經R時的下一跳節點NH（pj）為fi流經R 時的上一跳節點Preh（pi）的鄰節點，就可以判定流fi，fj的數據可以編碼，如果節點R 處存儲的關于流fi，fj路由信息表項PathTable（fi），PathTable（fj）未發生變化，且節點R維護的與流fi，fj有關的局部拓撲信息未變化，就可以對2個數據流的數據包進行持續的編碼操作。

為了清楚的表述流間編碼，下面結合一個具體的例子進行說明。圖5中2個單播數據流f1：A →D 及f2：E→C。

（1）數據流fi，fj在傳輸初始階段按照2.2節中改進的HWMP協議尋找通信路徑路由。f1：A →R →D，f2：E→R →B →C，表1為節點R 處的主要的路由表項。表中的NHN （next hop neighbour）為新加的一條信息項，是R要傳輸的下一跳節點的鄰居節點 （除去R 外）可通過3.4節改進的RM－AODV 的Hello報文獲得。

表1 節點R 處部分路由表項

（2）但節點R 的緩存中有流f1的數據包p1i，流f2的數據包p2j時，根據節點R 處的路由表項 （表1）反應的各個數據包的上一跳和下一跳節點的信息，以及節點R 所維護的鄰節點信息可知：p1i的下一跳節點D 是p2j上一跳節點E的鄰節點p2j的下一跳節點B為p1i上一跳節點的鄰節點，滿足圖6中的編碼算法機會判定，可以進行網絡編碼。

于是節點R 可以發送編碼數據包p1i⊕p2j，則R 的所有鄰居節點A、B、D、E都可以收到該編碼包。

因為p1i的下一跳節點D 是p2j上一跳節點E 的鄰節點，所以節點D 可以偵聽到E 發的數據包p2j，因此節點D可以解碼。通過 （p1i⊕p2j）⊕p2j解 碼 操 作，節 點D 會得到發給自己的數據包p1i。同理，節點E 也可以通過解碼得到發給自己的數據包p2j。如果節點R 中存儲的與流f1，f2相關的路由表項沒有變化，且R 所維護的與f1，f2有關的局部鄰節點信息沒有變化，就可以持續的對流f1，f2進行編碼操作。

3.3 解碼算法

為了使收到編碼數據包的節點能夠識別出其中是否有發給自己的數據包，在編碼數據包頭部需要添加一個簡單的編碼包頭，如圖7所示。其中CodeType標明該數據包是否編碼，RA1和RA2是編碼包中每個源數據包的下一跳節點MAC地址；PKT＿ID 為源數據包的包ID 號，該ID 號有源數據包中的MAC地址及序列號所生成的hash值。

圖7 編碼頭格式

網絡中每個節點需要為每一個鄰節點建立一個緩存隊列，用來存儲收到的鄰節點的數據包。當網絡中一個節點收到一個編碼包時，首先查看編碼包頭，檢測自己是否是編碼包的接收端。如果是，就會檢查自己的鄰節點緩存隊列，看是否有解碼所需的數據包，如果有就進行相應的解碼操作，提取出發給自己的源數據包。

由于編碼包的發送時采用單播的形式，編碼包頭只包含一個節點的MAC 地址，發送編碼包的節點無法收到全部目的節點的確認信息［12］。因此這種通信方式是不可靠的，為了提高鏈路層通信的可靠性，要求編碼包頭所指定的接收節點都要向上一跳的發送者發送ACK 確認幀。發送編碼節點收到ACK 后將刪除ACK 確認幀中標明的PKT＿ID 相對應的源數據包，從而避免數據包的重傳。如果在一定的時間內未收到確認幀，為了降低丟包率，將把源數據包重新發送給未發確認幀的節點。

3.4 網絡節點局部拓撲信息維護

在3.2節所述的編碼算法中，編碼機會的探測是以核心節點上下行鄰節點的局部拓撲信息為基礎的。為了獲得節點的局部拓撲信息，本文采用對HWMP按需路由RM－AODV的HELLO報文擴展的方法。在RM－AODV 中，鄰節點間需要間隔性的互相發送HELLO 報文來確認彼此的連接狀態，以此來維護鄰節點間的信息，因此對HELLO 報文進行擴展所需要的開銷并不多。在擴展的HELLO 報文中，Neighbor－ID為以鄰節點MAC地址為key的32位hash值。

4 仿真及性能分析

本文對改進協議在NS－3［13，14］下進行仿真。實現環境：在100m×100m 范圍內隨機分布50個節點。其它參數見表2。

在仿真環境，節點間數據流為512byte的UDP包。

表2 仿真參數

圖8為網絡中隨著負載的增加系統吞吐量的變化。隨著網絡中數據流的增加，網絡吞吐量也隨之增大，當吞吐量達到峰值時，網絡中的數據包沖突將導致系統吞吐量的下降。從圖中可以看出，改進的協議吞吐量明顯優于原有的協議。這是因為改進的協議中使用的基于LBS信息的方案降低了網絡節點內部通信時核心節點處的數據包，從而降低了在核心節點處的數據擁塞；另外，無線網絡編碼的引入也使系統的吞吐量隨之增加。

圖8 網內節點通信網絡吞吐量

圖9為網絡中數據包投遞率，從圖中可以看出隨著網絡中數據流的增加，數據包在中繼節點沖突增加，導致數據包的投遞率也隨之下降。但是改進的協議的數據包投遞率明顯高于原有的協議，這是因為未改進的協議在節點內部通信時數據包集中于核心節點 （特別是根節點）處，從而導致網絡擁塞嚴重，數據包沖突增大，使丟包率增大，降低了數據包的投遞率。

圖10為隨著網絡中數據流的增加數據包的端到端時延。從圖中可以看出隨著數據流的增加，數據包的端到端時延隨著增加，這是因為網絡中通信量增大導致沖突的增加。而改進的HWMP 協議的端到端時延要優于為改進的協議，這是因為改進的HWMP 協議中使用了更加優化的路由判據使選擇的路徑更優，另外基于LBS消息的改進與原有的協議相比，網絡內部節點通信時選擇的路徑也是最優的，所以最終使得改進的協議優于原來的協議。

圖9 網內節點通信數據包投遞率

圖10 網內節點通信平均端到端時延

5 結束語

本文主要選定了IEEE 802.11s中關于無線Mesh網絡的默認路由協議HWMP 協議作為研究的對象。通過對原來的HWMP路由協議的改進，無線Mesh網絡內部節點通信時在保持HWMP 協議原來優勢的基礎上，使節點間的路徑達到最優，從而降低了網絡內部節點通信的端到端時延，提高了網絡性能。結合HWMP協議的基本特點，提出了基于HWMP協議的流間無線網絡編碼，并給出了具體的編碼算法和解碼算法。對HWMP協議中的RM－AODV［14］協議的HELLO報文進行了擴充，使其能攜帶鄰節點的基本信息與其它鄰節點進行交換，從而使鄰節點間能夠獲得兩跳內的局部拓撲信息，為流間無線網絡的編碼機會探測提供了依據。仿真結果表明，基于HWMP協議的無線流間編碼對提高無線Mesh網絡的性能是行之有效的。

［1］Dimitrios Koutsonikolas，Hu Y Charlie，Wang Chih－Chun.Pacifier：High－throughput，reliable multicast without“crying babies”in wireless Mesh networks ［C］／／Proceedings of the 28th IEEE Communications Society Conference on Computer Communications.IEEE，2009：2473－2481.

［2］Sun Xuemei，Li Chunqing，Zhang Mingwei.A QoS routing algorithm based on culture－particle swarm optimization in wireless Mesh networks ［C］／／Proceedings of 6th International Conference on Wireless Communications，Networking and Mobile Computing.IEEE，2010：1－4.

［3］Wang X，Lim AO.IEEE 802.11s wireless Mesh networks：Framework and challenges ［J］.Ad－Hoc Networks，2008，6（1）：32－40.

［4］Hu Xiaobing，Mark Leeson，Evor Hines.An effective genetic algorithm for network coding ［J］.Computers and Operations Research，2012，39 （5）：952－963.

［5］Da Gang G.Research on 802.11sRM－AODV path selection protocol［J］.Jiangxi Science，2010，2 （l）：31－40.

［6］Bakhshi Bahador，Siavash Khorsandi.Complexity and design of QoS routing algorithms in wireless Mesh networks ［J］.Computer Communications，2011，34 （14）：1722－1737.

［7］Pinheiro M，Sampaio S，Vasques F，et al.A DHT－based approach for path selection and message forwarding in IEEE 802.11sindustrial wireless MES－h networks ［C］／／IEEE Conference on Emerging Technologies ＆ Factory Automation.IEEE，2009：1－10.

［8］Kowalik K，Davis M.Why are there so many routing protocols for wireless Mesh networks ［C］／／Irish Signaland Systems Conference，2006.

［9］Sengupta S，Rayanchu S，Banerjee S.Network coding－aware routing in wireless networks［J］.IEEE／ACM Transactions on Networking，2010，18 （4）：1158－1170.

［10］Perkins C，Belding－Royer E，Das S.IETF RFC 3561：Ad Hoc on－demand distance vector（AODV）routing ［S］.2010.

［11］Dong Q，Wu J，Hu W，et al.Practical network coding in wireless networks ［C］／／Proceedings of the 13th Annual ACM International Conference on Mobilecomputing and Networking.ACM，2007：306－309.

［12］Dimitrios Koutsonikolas，Charlie Hu Y，Wang Chih－Chun.XCOR：Synergistic interflow network coding and opportunistic routing ［C］／／Proceedings of the ACM International Conference on Mobile Computing and Networking.ACM，2008：2980－2989.

［13］Xi Yufang，Edmund M Yeh.Distributed algorithms for minimum cost multicast with network coding ［J］.IEEE／ACM Transactions on Networking，2010，18 （2）：379－392.

［14］Yang Zhenyu，Li Ming，Lou Wenjing.R－Code：Network coding based reliable broadcast in wireless Mesh networks［J］.Ad Hoc Networks，2011，9 （5）：788－798.