【正文】 遵守此規(guī)定 □公開 □保密 ____年 作者簽名 _______________ 導(dǎo)師簽名_______________ 簽字日期 _______________ 簽字日期_______________ 第 1 章 緒論 11 研究意義 近年來隨著計算機網(wǎng)絡(luò)技術(shù)的不斷發(fā)展無線網(wǎng)絡(luò)技術(shù)越來越引起人們的 重視無線 Mesh 網(wǎng)絡(luò)作為一種新型的無線網(wǎng)絡(luò)技術(shù)成為人們研究的熱點 無線 Mesh 網(wǎng)絡(luò) Wireless Mesh Network WMN 也稱為多跳 Multihop 網(wǎng)絡(luò)與傳統(tǒng)的無線網(wǎng)絡(luò)不同 WMN 是一種全新的無線 網(wǎng)絡(luò)技術(shù)對于傳統(tǒng)的 無線局域網(wǎng) Wireless Local Area NetworksWLAN 又被稱為單跳網(wǎng)絡(luò)每個Client 端都可以通過一條無線鏈路來訪問此無線網(wǎng)絡(luò)其中此無線鏈路與接入點 Access Point AP 相連而在 WMN 中任意的無線設(shè)備節(jié)點都能夠同時作為路 由器和接入點在此網(wǎng)絡(luò)中每一個設(shè)備節(jié)點都能發(fā)送信號并且接收信號同時 每一個設(shè)備節(jié)點都能夠跟一個或者多個對等的節(jié)點直接進行通信 無線多跳 網(wǎng)絡(luò) 有很多 種形 式包括 無線自 組織 網(wǎng)絡(luò) Wireless Ad Hoc Network 無線傳感器網(wǎng)絡(luò) Wireless Sensor Networks WSN 無線 Mesh 網(wǎng)絡(luò) WMN 無線車載網(wǎng)絡(luò) Wireless Vehicular Networks WVN 等等因此無 線多跳網(wǎng)絡(luò)在軍事航空智能交通地質(zhì)勘探偏遠(yuǎn)地區(qū)互聯(lián)網(wǎng)接入等方面有 著非常廣泛的應(yīng)用但是由于無線網(wǎng)絡(luò)的鏈路動態(tài)性時變性和丟包特性導(dǎo)致 了無線鏈路的質(zhì)量一般比較差而且穩(wěn)定性較低并且由于無線網(wǎng)絡(luò)采用廣播方式 傳輸?shù)忍攸c 這都對提高無線多跳網(wǎng)絡(luò)的性能和安全性提出了很高的要求 無線 Mesh 網(wǎng)絡(luò)融合了 WLAN 和 Ad hoc 網(wǎng)絡(luò)的優(yōu)勢支持多點對多點的傳 輸是一種大容量高速率覆蓋范圍廣的網(wǎng)絡(luò)成為寬帶接入的一種有效手段 也就成為一個研究熱點問題然而同有線網(wǎng)絡(luò)相比無線 Mesh 網(wǎng)絡(luò)在性能和 服務(wù)質(zhì)量方面還有很大差距實現(xiàn)介質(zhì)共享的 MAC 協(xié)議是一個非常重要的因素 圖 11 表示在七層網(wǎng)絡(luò)模型中 MAC 層所處的位置由圖可以看出 MAC 層 屬于數(shù)據(jù)鏈路層它有兩種工作機制點協(xié)調(diào)功能和分布式協(xié)調(diào)功 能點協(xié)調(diào)功 能 PCF Point Coordination Function 又稱為無爭用服務(wù) PCF 使用 AP 集中控 制的接入算法將發(fā)送數(shù)據(jù)權(quán)輪流交給各個網(wǎng)站從而避免了沖突的產(chǎn)生傳統(tǒng)的 無線局域網(wǎng)采用的就是這種競爭機制為減少多個節(jié)點訪問同一個媒介時的碰撞 概率 IEEE80211 規(guī)定 MAC 層采用分布式協(xié)調(diào)功能 DCF Distribution Coordination Function 的訪問機制又稱為爭用服 務(wù) DCF 在每個節(jié)點處使用 CSMACA 載波偵聽沖突避免機制的分布式接入算法讓各個站點通過爭用 信道來獲取發(fā)送權(quán)在無線 Mesh 網(wǎng)絡(luò)中主要采用這種競爭機制 DCF 機制的 1 核心算法是二進制指數(shù)退避算法 BEB 避免節(jié)點之間的來回碰撞由于無論 在理論上還是實踐中當(dāng)競爭節(jié)點數(shù)增加時應(yīng)用二進制指數(shù)退避算法的 MAC 層協(xié)議都存在著公平因子平均時延網(wǎng)絡(luò)吞吐量等參數(shù)惡化的問題所以自從 二進制指數(shù)退避算法被應(yīng)用 到 80211 協(xié)議 MAC 層后就一直成為研究的熱點問 題李云隆克平趙為糧等 2020 陳羽中俞能海開彩紅等 2020 劉瑞 珺周安棟陳晶 2020 傳統(tǒng)的 DCF 機制已經(jīng)不適用于無線 Mesh 網(wǎng)絡(luò)因 此對無線 Mesh 網(wǎng)絡(luò) MAC 層的研究具有重要的意義 應(yīng)用層 表示層 會 話層 傳輸層 網(wǎng)絡(luò)層 數(shù)據(jù)鏈路層 LLC 邏輯鏈路控制子層 MAC 介質(zhì)訪問控制子層 物理層 圖 11 七層網(wǎng)絡(luò)模型 隨著網(wǎng)絡(luò)通信的飛速發(fā)展普通的傳輸方式已經(jīng)滿足人們對數(shù)據(jù)傳輸?shù)男? 求網(wǎng)絡(luò)編碼作為一種新型而且有效的傳輸方式逐漸成為人們研究的熱點網(wǎng) 絡(luò)編碼從網(wǎng)絡(luò)總體和系統(tǒng)性能的角度出發(fā)能夠很有效解決網(wǎng)絡(luò)的路由選擇策略 和如何獲得網(wǎng)絡(luò)的最大流量等相關(guān)問題隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展和網(wǎng)絡(luò)規(guī)模的 不斷擴大從網(wǎng)絡(luò)的傳輸效率節(jié)點能耗寬帶接入到網(wǎng)絡(luò)的可靠性魯棒性 安全性等方面要求也越來越高而網(wǎng)絡(luò)編碼作為一種新 型的信息傳輸方式可 以通過對需要在網(wǎng)絡(luò)節(jié)點上傳送的消息進行適當(dāng)?shù)木€性編碼或非線性編碼處理 來有效的改善網(wǎng)絡(luò)的傳輸性能因而受到了廣泛重視成為當(dāng)前網(wǎng)絡(luò)信息論中一 個重要的研究方向張巖 2020 研究網(wǎng)絡(luò)編碼中優(yōu)化問題的意義在于 1 推動了支持網(wǎng)絡(luò)編碼的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的設(shè)計 原始 Inter 中的數(shù)據(jù)流業(yè)務(wù)是主要應(yīng)用于單播網(wǎng)絡(luò)的因此在構(gòu)建網(wǎng)絡(luò)拓 2 撲結(jié)構(gòu)和搭建路由架構(gòu)和設(shè)計 路由協(xié)議的時候基本都是考慮單播情況的但是隨 著網(wǎng)絡(luò)中組播業(yè)務(wù)的普及在設(shè)計網(wǎng)絡(luò)拓?fù)湓氐臅r候我們需要更多地考慮它 們?nèi)绾文軌蚋玫刂С纸M播業(yè)務(wù)中的數(shù)據(jù)分發(fā)技術(shù)最近被廣泛研究的網(wǎng)絡(luò)編碼 作為一種新型的信息傳輸方式成為傳輸組播業(yè)務(wù)數(shù)據(jù)的最佳方式之一采用網(wǎng)絡(luò) 編碼方式將大大推進網(wǎng)絡(luò)編碼理論在實際組播業(yè)務(wù)中的應(yīng)用黃政王新 2020 2 為優(yōu)化路由選擇提供新的理論框架 在路由網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中建立有向和無向網(wǎng)絡(luò)中的組播路由問題屬于 NP 完全 問題很難進行求解最多只能采用近 似算法或啟發(fā)式算法進行求解然而同樣 的問題在引入網(wǎng)絡(luò)編碼后便轉(zhuǎn)換成了線性規(guī)劃問題方便了求解過程可以設(shè)計 有關(guān)多項式時間內(nèi)的有效算法進行求解考慮如何為最佳編碼子圖的選擇最優(yōu)的 設(shè)計分布式的算法將推動網(wǎng)絡(luò)編碼路由協(xié)議的優(yōu)化設(shè)計黃政王新 2020 由于無線 Mesh 網(wǎng)絡(luò)的廣播特性和其他自身特性在減少編碼控制和計算開 銷等方面可以獲得很好的解決方法因而無線 Mesh 網(wǎng)絡(luò)中針對網(wǎng)絡(luò)編碼的研究 具有非常重要的意義 12 國內(nèi)外研究現(xiàn)狀 對于無線 Mesh 網(wǎng)絡(luò)的研究主要 集中于路由層面和 MAC 層面其中路由層 主要包括通過優(yōu)化機會路由來提高網(wǎng)絡(luò)性能具體方法包括路由調(diào)度和轉(zhuǎn)發(fā)選擇 等其中典型的協(xié)議包括 EXOR Sanjit Biswas Robert Morris 2020 SOAR Seshadri Jayesh Mehta et al 2020 等針對無線網(wǎng)絡(luò) MAC 層面的研究主要 是針對 PCF 和 DCF 競爭機制的優(yōu)化和最新研究的將網(wǎng)絡(luò)編碼應(yīng)用于 MAC 層的 優(yōu)化策略 無線 Mesh 網(wǎng)絡(luò)中 DCF 退避機制的核心是二進制退避算法然而這種退避 算法自從被提出以來就產(chǎn)生了很大爭議成為人們研究的熱點針對 80211 協(xié) 議中 MAC 層的二進制退避算法存在的種種弊端新的研究成果不斷涌現(xiàn)文獻 Cali FConti MGregori E 2020 中運用估計的方法對退避窗口進行調(diào)整 文獻 Bharghvan V 1998 中針對退避窗口的變化展開研究文獻 Bianehi G 2020 中用馬爾可夫鏈建立的模型 無線網(wǎng)絡(luò)編碼作為一種全新的傳輸方式也是近幾年來研究的熱點而且采 用 網(wǎng)絡(luò)編碼的方式能夠很好的增加網(wǎng)絡(luò)吞吐量提高網(wǎng)絡(luò)性能網(wǎng)絡(luò)編碼是一個在 中間節(jié)點合并多個數(shù)據(jù)流并可在目的節(jié)點恢復(fù)數(shù)據(jù)流的技術(shù)可以減少介質(zhì)中的 傳輸次數(shù)在無線網(wǎng)絡(luò)環(huán)境中網(wǎng)絡(luò)編碼可以在多個層實現(xiàn)比如模擬網(wǎng)絡(luò)編 3 碼可在 PHY 層的符號層實現(xiàn)也可以在 MAC 層的 byte 層和 MAC 層之上的packet 層實現(xiàn)在這幾種實現(xiàn)方式中在 packet 層實現(xiàn)網(wǎng)絡(luò)編碼較容易在當(dāng)前的無線平 臺上擴展 Rayanchu Shravan Sen Sayandeep Wu Jianminq et al 2020 網(wǎng)絡(luò)編碼可以分為流間編碼 interflow 和流內(nèi)編碼 intraflow 兩種 COPE Katti S Rahul H Hu W et al 2020 S Katti D Katabi W Hu et al 2020 和 BEND Jian Zhang Yuanzhu Peter Chen and Ivan Marsic 2020 是 interflow 的兩種典型協(xié)議在 SIGCOMM06Sachin Katti 等提出了 COPE 協(xié)議 但是由于在 COPE 協(xié)議中編碼路徑和編碼節(jié)點由路由層確定中間節(jié)點只能被 動的等待編碼機會大大限制了編碼機會的利用率在 Computer Networks10 Jian Zhang 等人提出了 BEND 協(xié)議該協(xié)議將機會轉(zhuǎn)發(fā)和網(wǎng)絡(luò)編碼結(jié)合使得傳 輸過程中節(jié)點能夠獲得更多的編碼機會從而提高了網(wǎng)絡(luò)吞吐量 MORE ChachulskiSzymon Jennings Michael Katti Sachin et al 2020 是intraflow 的典 型協(xié)議它是一個獨立于 MAC 層的機會路由協(xié)議中間節(jié)點在收到數(shù)據(jù)包后 隨機編碼這些包然后發(fā)送出去可以很好的實現(xiàn)機會路由和網(wǎng)絡(luò)編碼協(xié)同提高 網(wǎng)絡(luò)吞吐量 通過對以上網(wǎng)絡(luò)編碼協(xié)議的分析我們得出 COPE 是一種 lossfree 的網(wǎng)絡(luò) 協(xié)議是一種比較理想的假設(shè)條件 BEND 協(xié)議是在 COPE 協(xié)議基礎(chǔ)上針對鏈 路損失比較嚴(yán)重情況下設(shè)計的一種網(wǎng)絡(luò)編碼協(xié)議但是他非常依賴于 目的節(jié)點的 無意偵聽 overhear 在網(wǎng)絡(luò)繁忙時無意偵聽的成功率會大大降低因此會對 協(xié)議性能造成巨大影響 COPEdup 協(xié)議重復(fù)發(fā)送一次編碼包而美國威斯康星 ˙麥迪遜大學(xué)的 Shravan Rayanchu 等人的方法只是由中間節(jié)點簡單重復(fù)發(fā)送編 碼包如果目標(biāo)節(jié)點的偵聽失敗則不管重復(fù)多少次編碼包都不能實現(xiàn)解碼 以上提出的幾種典型的編碼方式假設(shè)了一種較理想的網(wǎng)絡(luò)環(huán)境即lossfree 或者丟包率較低然而實際的無線網(wǎng)絡(luò)環(huán)境中丟包是不可避免的而且大約在 30 左右甚 至更高 Rayanchu Shravan Sen Sayandeep Wu Jianminq et a l 2020 在網(wǎng)絡(luò)鏈路丟包大的情況下采用原有的編碼協(xié)議編碼和解碼機會都將大大減 少這導(dǎo)致了編碼解碼效率的嚴(yán)重下降因此提出一種適用于丟包率較大的 無線 Mesh 網(wǎng)絡(luò)環(huán)境的編碼協(xié)議具有重要意義 13 研究內(nèi)容和目標(biāo) 實際無線網(wǎng)絡(luò)環(huán)境丟包率一