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

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

0 引 言

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

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

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

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

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

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

在HWMP協(xié)議的先驗(yàn)式生成樹(shù)路由模式中，如果源節(jié)點(diǎn)沒(méi)有到目的節(jié)點(diǎn)的路徑，源節(jié)點(diǎn)不會(huì)發(fā)起路徑查找而是將數(shù)據(jù)直接發(fā)給父節(jié)點(diǎn)。父節(jié)點(diǎn)收到數(shù)據(jù)包后會(huì)首先查看目的地址是否是自己的子節(jié)點(diǎn)，如果是則轉(zhuǎn)發(fā)數(shù)據(jù)，如果不是則繼續(xù)向上層父節(jié)點(diǎn)轉(zhuǎn)發(fā)。當(dāng)根節(jié)點(diǎn)MPP［5］收到數(shù)據(jù)包后會(huì)查看目的地址是否在Mesh網(wǎng)內(nèi)部，如果是則通過(guò)先驗(yàn)樹(shù)轉(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)通信時(shí)，將會(huì)因?yà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í)的情形。假設(shè)根節(jié)點(diǎn)MPP為1，源節(jié)點(diǎn)為4，目的節(jié)點(diǎn)為6，按照先驗(yàn)式生成樹(shù)建立起來(lái)的節(jié)點(diǎn)4和節(jié)點(diǎn)6之間的路徑為4—2—1—3—6，這時(shí)即使兩節(jié)點(diǎn)間存在最優(yōu)路徑4—5—6，數(shù)據(jù)仍然是按4—2—1—3—6進(jìn)行轉(zhuǎn)發(fā)［6］，從而造成數(shù)據(jù)的時(shí)延和網(wǎng)絡(luò)吞吐量的降低。

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

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

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

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

（1）根節(jié)點(diǎn)MPP 生成RANN 消息：先驗(yàn)式生成樹(shù)建立時(shí)，根節(jié)點(diǎn)將根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的MAC地址建立hash表，以hash表中的hash值為基礎(chǔ)建立LBS信息庫(kù)。將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 時(shí)首先查看RANN 中的Changed B0位，當(dāng)B0位為0，如果CRC與本地LBS的CRC值相同則忽略，否則將向根節(jié)點(diǎn)MP 發(fā)送請(qǐng)求LBS 的RLBS 幀；當(dāng)B0 位為1時(shí)，將提取LBS更新節(jié)點(diǎn)本地的LBS庫(kù)。

為了同步Mesh節(jié)點(diǎn)和根節(jié)點(diǎn)MP的LBS信息，Mesh節(jié)點(diǎn)可以向根節(jié)點(diǎn)MPP發(fā)送RLBS （Request LBS）幀，主動(dòng)請(qǐng)求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，通過(guò)hash 函數(shù)得出相應(yīng)的hashID 值，如果該值不存在本地LBS信息庫(kù)中，源節(jié)點(diǎn)將把數(shù)據(jù)發(fā)給根節(jié)點(diǎn)MPP。否則源節(jié)點(diǎn)將把數(shù)據(jù)發(fā)給父節(jié)點(diǎn)，通過(guò)中間節(jié)點(diǎn)直接通信，同時(shí)源節(jié)點(diǎn)發(fā)出PREQ 消息開(kāi)始新的路徑發(fā)現(xiàn)過(guò)程。當(dāng)源節(jié)點(diǎn)收到目的節(jié)點(diǎn)返回的RREP消息后，如果得到的新路徑優(yōu)于現(xiàn)有的路徑，將使用新路徑建立起與目的節(jié)點(diǎn)通信。通過(guò)這種新的路徑選擇算法，即保留了原有路徑選擇的優(yōu)勢(shì)，同時(shí)又可使網(wǎng)內(nèi)節(jié)點(diǎn)間通信時(shí)可以找到最優(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ī)會(huì)主義網(wǎng)絡(luò)編碼

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

圖5是無(wú)線Mesh網(wǎng)絡(luò)先驗(yàn)式生成樹(shù)的一部分，核心節(jié)點(diǎn)為R，在COPE［9］中是采用鄰節(jié)點(diǎn)間不斷的交換接收?qǐng)?bào)告來(lái)確定編碼機(jī)會(huì)的，這需要浪費(fèi)很大的帶寬，而一旦接收?qǐng)?bào)告丟失或者延遲也將導(dǎo)致無(wú)法進(jìn)行最優(yōu)編碼。但在無(wú)線Mesh網(wǎng)絡(luò)中，對(duì)于經(jīng)過(guò)核心節(jié)點(diǎn)的數(shù)據(jù)流，如果知道兩條數(shù)據(jù)流的下一跳節(jié)點(diǎn)是鄰節(jié)點(diǎn)，就可以判斷兩個(gè)節(jié)點(diǎn)間可以互相偵聽(tīng)到對(duì)方發(fā)送的數(shù)據(jù)包，核心節(jié)點(diǎn)也就可以據(jù)此對(duì)這兩條數(shù)據(jù)流數(shù)據(jù)包進(jìn)行編碼。從而省去了不斷傳輸鄰節(jié)點(diǎn)間接收?qǐng)?bào)告。以圖5為例，數(shù)據(jù)流f1，f2都經(jīng)過(guò)核心節(jié)點(diǎn)R，通過(guò)獲知鄰節(jié)點(diǎn)A、B、D、E 的鄰節(jié)點(diǎn)信息可知流f1和流f2的下一跳節(jié)點(diǎn)之間互為鄰節(jié)點(diǎn)，這也就意味著A、B，D、E兩對(duì)節(jié)點(diǎn)都分別可以偵聽(tīng)到對(duì)方發(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ú)線網(wǎng)絡(luò)編碼是在HWMP 協(xié)議先驗(yàn)式生成樹(shù)的基礎(chǔ)上，利用到根節(jié)點(diǎn)的生成樹(shù)的路由表項(xiàng)來(lái)探測(cè)每個(gè)節(jié)點(diǎn)的編碼機(jī)會(huì)，對(duì)于有編碼機(jī)會(huì)的核心節(jié)點(diǎn)如果滿足條件，就對(duì)經(jīng)過(guò)核心節(jié)點(diǎn)的數(shù)據(jù)流進(jìn)行編碼，從而提高網(wǎng)絡(luò)的吞吐量。流間網(wǎng)絡(luò)編碼主要用于無(wú)線Mesh網(wǎng)絡(luò)基礎(chǔ)網(wǎng)絡(luò)架構(gòu)，只要編碼的節(jié)點(diǎn)所存儲(chǔ)的與編碼多個(gè)數(shù)據(jù)流相關(guān)的路由表項(xiàng)沒(méi)變化，且編碼節(jié)點(diǎn)與鄰節(jié)點(diǎn)的拓?fù)滏溄訝顩r良好，就可以對(duì)滿足條件的數(shù)據(jù)流進(jìn)行持續(xù)的相似編碼操作，而不像現(xiàn)有的面向數(shù)據(jù)包的算法一樣對(duì)每個(gè)數(shù)據(jù)包都要進(jìn)行編碼條件判斷［11］。

3.2 編碼算法

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

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

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

假設(shè)網(wǎng)絡(luò)中存在一個(gè)核心節(jié)點(diǎn)R，數(shù)據(jù)流fi，fj流經(jīng)R，此時(shí)R 通過(guò)編碼判定就可以決定是否可以對(duì)流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)時(shí)，首先會(huì)探測(cè)編碼的機(jī)會(huì)，如果fi流經(jīng)R 時(shí)的下一跳節(jié)點(diǎn)NH（pi）為fj流經(jīng)R時(shí)的上一跳節(jié)點(diǎn)PreH（pj）的鄰節(jié)點(diǎn)，且如果fj流經(jīng)R時(shí)的下一跳節(jié)點(diǎn)NH（pj）為fi流經(jīng)R 時(shí)的上一跳節(jié)點(diǎn)Preh（pi）的鄰節(jié)點(diǎn)，就可以判定流fi，fj的數(shù)據(jù)可以編碼，如果節(jié)點(diǎn)R 處存儲(chǔ)的關(guān)于流fi，fj路由信息表項(xiàng)PathTable（fi），PathTable（fj）未發(fā)生變化，且節(jié)點(diǎn)R維護(hù)的與流fi，fj有關(guān)的局部拓?fù)湫畔⑽醋兓?，就可以?duì)2個(gè)數(shù)據(jù)流的數(shù)據(jù)包進(jìn)行持續(xù)的編碼操作。

為了清楚的表述流間編碼，下面結(jié)合一個(gè)具體的例子進(jìn)行說(shuō)明。圖5中2個(gè)單播數(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 處的主要的路由表項(xiàng)。表中的NHN （next hop neighbour）為新加的一條信息項(xiàng)，是R要傳輸?shù)南乱惶?jié)點(diǎn)的鄰居節(jié)點(diǎn) （除去R 外）可通過(guò)3.4節(jié)改進(jìn)的RM－AODV 的Hello報(bào)文獲得。

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

（2）但節(jié)點(diǎn)R 的緩存中有流f1的數(shù)據(jù)包p1i，流f2的數(shù)據(jù)包p2j時(shí)，根據(jù)節(jié)點(diǎn)R 處的路由表項(xiàng) （表1）反應(yīng)的各個(gè)數(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ī)會(huì)判定，可以進(jìn)行網(wǎng)絡(luò)編碼。

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

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

3.3 解碼算法

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

圖7 編碼頭格式

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

由于編碼包的發(fā)送時(shí)采用單播的形式，編碼包頭只包含一個(gè)節(jié)點(diǎn)的MAC 地址，發(fā)送編碼包的節(jié)點(diǎn)無(wú)法收到全部目的節(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 相對(duì)應(yīng)的源數(shù)據(jù)包，從而避免數(shù)據(jù)包的重傳。如果在一定的時(shí)間內(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ī)會(huì)的探測(cè)是以核心節(jié)點(diǎn)上下行鄰節(jié)點(diǎn)的局部拓?fù)湫畔榛A(chǔ)的。為了獲得節(jié)點(diǎn)的局部拓?fù)湫畔?，本文采用?duì)HWMP按需路由RM－AODV的HELLO報(bào)文擴(kuò)展的方法。在RM－AODV 中，鄰節(jié)點(diǎn)間需要間隔性的互相發(fā)送HELLO 報(bào)文來(lái)確認(rèn)彼此的連接狀態(tài)，以此來(lái)維護(hù)鄰節(jié)點(diǎn)間的信息，因此對(duì)HELLO 報(bào)文進(jìn)行擴(kuò)展所需要的開(kāi)銷并不多。在擴(kuò)展的HELLO 報(bào)文中，Neighbor－ID為以鄰節(jié)點(diǎn)MAC地址為key的32位hash值。

4 仿真及性能分析

本文對(duì)改進(jìn)協(xié)議在NS－3［13，14］下進(jìn)行仿真。實(shí)現(xiàn)環(huán)境：在100m×100m 范圍內(nèi)隨機(jī)分布50個(gè)節(jié)點(diǎn)。其它參數(shù)見(jiàn)表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á)到峰值時(shí)，網(wǎng)絡(luò)中的數(shù)據(jù)包沖突將導(dǎo)致系統(tǒng)吞吐量的下降。從圖中可以看出，改進(jìn)的協(xié)議吞吐量明顯優(yōu)于原有的協(xié)議。這是因?yàn)楦倪M(jìn)的協(xié)議中使用的基于LBS信息的方案降低了網(wǎng)絡(luò)節(jié)點(diǎn)內(nèi)部通信時(shí)核心節(jié)點(diǎn)處的數(shù)據(jù)包，從而降低了在核心節(jié)點(diǎn)處的數(shù)據(jù)擁塞；另外，無(wú)線網(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é)議，這是因?yàn)槲锤倪M(jìn)的協(xié)議在節(jié)點(diǎn)內(nèi)部通信時(shí)數(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í)延。從圖中可以看出隨著數(shù)據(jù)流的增加，數(shù)據(jù)包的端到端時(shí)延隨著增加，這是因?yàn)榫W(wǎng)絡(luò)中通信量增大導(dǎo)致沖突的增加。而改進(jìn)的HWMP 協(xié)議的端到端時(shí)延要優(yōu)于為改進(jìn)的協(xié)議，這是因?yàn)楦倪M(jìn)的HWMP 協(xié)議中使用了更加優(yōu)化的路由判據(jù)使選擇的路徑更優(yōu)，另外基于LBS消息的改進(jìn)與原有的協(xié)議相比，網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)通信時(shí)選擇的路徑也是最優(yōu)的，所以最終使得改進(jìn)的協(xié)議優(yōu)于原來(lái)的協(xié)議。

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

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

5 結(jié)束語(yǔ)

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