龍昭華，秦曉煥，劉達(dá)明，2

（1.重慶郵電大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，重慶400065；2.重慶郵電大學(xué) 移通學(xué)院，重慶401520）

0 引 言

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

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

1 HWMP協(xié)議中存在的問題

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

2 基于LBS的HWMP協(xié)議改進(jìn)

2.1 現(xiàn)有的路由協(xié)議介紹

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

圖1 無線Mesh網(wǎng)內(nèi)部節(jié)點(diǎn)通信

2.2 改進(jìn)的路由協(xié)議

HWMP先驗式生成樹路由模式在Mesh 網(wǎng)絡(luò)節(jié)點(diǎn)與外部網(wǎng)的通信情境中有很大的優(yōu)勢；而按需路由模式則在Mesh網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)的通信中占優(yōu)勢。因此，需要把兩種模式的優(yōu)點(diǎn)結(jié)合起來找到適合上述兩種通信方式的最佳路徑。

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

（1）根節(jié)點(diǎn)MPP 生成RANN 消息：先驗式生成樹建立時，根節(jié)點(diǎn)將根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的MAC地址建立hash表，以hash表中的hash值為基礎(chǔ)建立LBS信息庫。將LBS及其CRC加入RANN 中廣播到Mesh網(wǎng)絡(luò)中。如果本地LBS未改變將只在RANN 中加入LBS的CRC值。

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

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

改進(jìn)的Mesh 網(wǎng)內(nèi)節(jié)點(diǎn)間路徑選擇算法偽代碼如圖4所示。

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

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

圖3 HWMP RLBS幀格式

圖4 改進(jìn)的HWMP路徑選擇算法

3 HWMP協(xié)議中的機(jī)會主義網(wǎng)絡(luò)編碼

在無線Mesh網(wǎng)絡(luò)的網(wǎng)絡(luò)架構(gòu)中，因為Mesh節(jié)點(diǎn)大部分都是固定的，所以網(wǎng)絡(luò)拓?fù)湟蚕鄬Ψ€(wěn)定［8，10］。當(dāng)HWMP中基于先驗式的生成樹建立后，網(wǎng)絡(luò)中就會存在多個核心節(jié)點(diǎn)，在這些核心節(jié)點(diǎn)上將會有多個數(shù)據(jù)流通過，這就給核心節(jié)點(diǎn)進(jìn)行流間編碼創(chuàng)造了機(jī)會。

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

圖5 基于HWMP協(xié)議流間編碼示例

3.1 HWMP協(xié)議流間網(wǎng)絡(luò)編碼算法

流間無線網(wǎng)絡(luò)編碼是在HWMP 協(xié)議先驗式生成樹的基礎(chǔ)上，利用到根節(jié)點(diǎn)的生成樹的路由表項來探測每個節(jié)點(diǎn)的編碼機(jī)會，對于有編碼機(jī)會的核心節(jié)點(diǎn)如果滿足條件，就對經(jīng)過核心節(jié)點(diǎn)的數(shù)據(jù)流進(jìn)行編碼，從而提高網(wǎng)絡(luò)的吞吐量。流間網(wǎng)絡(luò)編碼主要用于無線Mesh網(wǎng)絡(luò)基礎(chǔ)網(wǎng)絡(luò)架構(gòu)，只要編碼的節(jié)點(diǎn)所存儲的與編碼多個數(shù)據(jù)流相關(guān)的路由表項沒變化，且編碼節(jié)點(diǎn)與鄰節(jié)點(diǎn)的拓?fù)滏溄訝顩r良好，就可以對滿足條件的數(shù)據(jù)流進(jìn)行持續(xù)的相似編碼操作，而不像現(xiàn)有的面向數(shù)據(jù)包的算法一樣對每個數(shù)據(jù)包都要進(jìn)行編碼條件判斷［11］。

3.2 編碼算法

流間網(wǎng)絡(luò)編碼是在HWMP 先驗式生成樹的基礎(chǔ)上，充分利用網(wǎng)絡(luò)中節(jié)點(diǎn)所維護(hù)的路由表項來探測編碼的機(jī)會。具體的算法流程如下：

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

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

假設(shè)網(wǎng)絡(luò)中存在一個核心節(jié)點(diǎn)R，數(shù)據(jù)流fi，fj流經(jīng)R，此時R 通過編碼判定就可以決定是否可以對流fi數(shù)據(jù)包pifj數(shù)據(jù)包pj進(jìn)行編碼操作。

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

圖6 流間網(wǎng)絡(luò)編碼算法

當(dāng)節(jié)點(diǎn)R 發(fā)現(xiàn)fi，fj流經(jīng)時，首先會探測編碼的機(jī)會，如果fi流經(jīng)R 時的下一跳節(jié)點(diǎn)NH（pi）為fj流經(jīng)R時的上一跳節(jié)點(diǎn)PreH（pj）的鄰節(jié)點(diǎn)，且如果fj流經(jīng)R時的下一跳節(jié)點(diǎn)NH（pj）為fi流經(jīng)R 時的上一跳節(jié)點(diǎn)Preh（pi）的鄰節(jié)點(diǎn)，就可以判定流fi，fj的數(shù)據(jù)可以編碼，如果節(jié)點(diǎn)R 處存儲的關(guān)于流fi，fj路由信息表項PathTable（fi），PathTable（fj）未發(fā)生變化，且節(jié)點(diǎn)R維護(hù)的與流fi，fj有關(guān)的局部拓?fù)湫畔⑽醋兓涂梢詫?個數(shù)據(jù)流的數(shù)據(jù)包進(jìn)行持續(xù)的編碼操作。

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

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

表1 節(jié)點(diǎn)R 處部分路由表項

（2）但節(jié)點(diǎn)R 的緩存中有流f1的數(shù)據(jù)包p1i，流f2的數(shù)據(jù)包p2j時，根據(jù)節(jié)點(diǎn)R 處的路由表項 （表1）反應(yīng)的各個數(shù)據(jù)包的上一跳和下一跳節(jié)點(diǎn)的信息，以及節(jié)點(diǎn)R 所維護(hù)的鄰節(jié)點(diǎn)信息可知：p1i的下一跳節(jié)點(diǎn)D 是p2j上一跳節(jié)點(diǎn)E的鄰節(jié)點(diǎn)p2j的下一跳節(jié)點(diǎn)B為p1i上一跳節(jié)點(diǎn)的鄰節(jié)點(diǎn)，滿足圖6中的編碼算法機(jī)會判定，可以進(jìn)行網(wǎng)絡(luò)編碼。

于是節(jié)點(diǎn)R 可以發(fā)送編碼數(shù)據(jù)包p1i⊕p2j，則R 的所有鄰居節(jié)點(diǎn)A、B、D、E都可以收到該編碼包。

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

3.3 解碼算法

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

圖7 編碼頭格式

網(wǎng)絡(luò)中每個節(jié)點(diǎn)需要為每一個鄰節(jié)點(diǎn)建立一個緩存隊列，用來存儲收到的鄰節(jié)點(diǎn)的數(shù)據(jù)包。當(dāng)網(wǎng)絡(luò)中一個節(jié)點(diǎn)收到一個編碼包時，首先查看編碼包頭，檢測自己是否是編碼包的接收端。如果是，就會檢查自己的鄰節(jié)點(diǎn)緩存隊列，看是否有解碼所需的數(shù)據(jù)包，如果有就進(jìn)行相應(yīng)的解碼操作，提取出發(fā)給自己的源數(shù)據(jù)包。

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

3.4 網(wǎng)絡(luò)節(jié)點(diǎn)局部拓?fù)湫畔⒕S護(hù)

在3.2節(jié)所述的編碼算法中，編碼機(jī)會的探測是以核心節(jié)點(diǎn)上下行鄰節(jié)點(diǎn)的局部拓?fù)湫畔榛A(chǔ)的。為了獲得節(jié)點(diǎn)的局部拓?fù)湫畔ⅲ疚牟捎脤WMP按需路由RM－AODV的HELLO報文擴(kuò)展的方法。在RM－AODV 中，鄰節(jié)點(diǎn)間需要間隔性的互相發(fā)送HELLO 報文來確認(rèn)彼此的連接狀態(tài)，以此來維護(hù)鄰節(jié)點(diǎn)間的信息，因此對HELLO 報文進(jìn)行擴(kuò)展所需要的開銷并不多。在擴(kuò)展的HELLO 報文中，Neighbor－ID為以鄰節(jié)點(diǎn)MAC地址為key的32位hash值。

4 仿真及性能分析

本文對改進(jìn)協(xié)議在NS－3［13，14］下進(jìn)行仿真。實現(xiàn)環(huán)境：在100m×100m 范圍內(nèi)隨機(jī)分布50個節(jié)點(diǎn)。其它參數(shù)見表2。

在仿真環(huán)境，節(jié)點(diǎn)間數(shù)據(jù)流為512byte的UDP包。

表2 仿真參數(shù)

圖8為網(wǎng)絡(luò)中隨著負(fù)載的增加系統(tǒng)吞吐量的變化。隨著網(wǎng)絡(luò)中數(shù)據(jù)流的增加，網(wǎng)絡(luò)吞吐量也隨之增大，當(dāng)吞吐量達(dá)到峰值時，網(wǎng)絡(luò)中的數(shù)據(jù)包沖突將導(dǎo)致系統(tǒng)吞吐量的下降。從圖中可以看出，改進(jìn)的協(xié)議吞吐量明顯優(yōu)于原有的協(xié)議。這是因為改進(jìn)的協(xié)議中使用的基于LBS信息的方案降低了網(wǎng)絡(luò)節(jié)點(diǎn)內(nèi)部通信時核心節(jié)點(diǎn)處的數(shù)據(jù)包，從而降低了在核心節(jié)點(diǎn)處的數(shù)據(jù)擁塞；另外，無線網(wǎng)絡(luò)編碼的引入也使系統(tǒng)的吞吐量隨之增加。

圖8 網(wǎng)內(nèi)節(jié)點(diǎn)通信網(wǎng)絡(luò)吞吐量

圖9為網(wǎng)絡(luò)中數(shù)據(jù)包投遞率，從圖中可以看出隨著網(wǎng)絡(luò)中數(shù)據(jù)流的增加，數(shù)據(jù)包在中繼節(jié)點(diǎn)沖突增加，導(dǎo)致數(shù)據(jù)包的投遞率也隨之下降。但是改進(jìn)的協(xié)議的數(shù)據(jù)包投遞率明顯高于原有的協(xié)議，這是因為未改進(jìn)的協(xié)議在節(jié)點(diǎn)內(nèi)部通信時數(shù)據(jù)包集中于核心節(jié)點(diǎn) （特別是根節(jié)點(diǎn)）處，從而導(dǎo)致網(wǎng)絡(luò)擁塞嚴(yán)重，數(shù)據(jù)包沖突增大，使丟包率增大，降低了數(shù)據(jù)包的投遞率。

圖10為隨著網(wǎng)絡(luò)中數(shù)據(jù)流的增加數(shù)據(jù)包的端到端時延。從圖中可以看出隨著數(shù)據(jù)流的增加，數(shù)據(jù)包的端到端時延隨著增加，這是因為網(wǎng)絡(luò)中通信量增大導(dǎo)致沖突的增加。而改進(jìn)的HWMP 協(xié)議的端到端時延要優(yōu)于為改進(jìn)的協(xié)議，這是因為改進(jìn)的HWMP 協(xié)議中使用了更加優(yōu)化的路由判據(jù)使選擇的路徑更優(yōu)，另外基于LBS消息的改進(jìn)與原有的協(xié)議相比，網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)通信時選擇的路徑也是最優(yōu)的，所以最終使得改進(jìn)的協(xié)議優(yōu)于原來的協(xié)議。

圖9 網(wǎng)內(nèi)節(jié)點(diǎn)通信數(shù)據(jù)包投遞率

圖10 網(wǎng)內(nèi)節(jié)點(diǎn)通信平均端到端時延

5 結(jié)束語

本文主要選定了IEEE 802.11s中關(guān)于無線Mesh網(wǎng)絡(luò)的默認(rèn)路由協(xié)議HWMP 協(xié)議作為研究的對象。通過對原來的HWMP路由協(xié)議的改進(jìn)，無線Mesh網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)通信時在保持HWMP 協(xié)議原來優(yōu)勢的基礎(chǔ)上，使節(jié)點(diǎn)間的路徑達(dá)到最優(yōu)，從而降低了網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)通信的端到端時延，提高了網(wǎng)絡(luò)性能。結(jié)合HWMP協(xié)議的基本特點(diǎn)，提出了基于HWMP協(xié)議的流間無線網(wǎng)絡(luò)編碼，并給出了具體的編碼算法和解碼算法。對HWMP協(xié)議中的RM－AODV［14］協(xié)議的HELLO報文進(jìn)行了擴(kuò)充，使其能攜帶鄰節(jié)點(diǎn)的基本信息與其它鄰節(jié)點(diǎn)進(jìn)行交換，從而使鄰節(jié)點(diǎn)間能夠獲得兩跳內(nèi)的局部拓?fù)湫畔?，為流間無線網(wǎng)絡(luò)的編碼機(jī)會探測提供了依據(jù)。仿真結(jié)果表明，基于HWMP協(xié)議的無線流間編碼對提高無線Mesh網(wǎng)絡(luò)的性能是行之有效的。

［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(huán) 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.