1、無線Mesh 網(wǎng)絡(luò)路由選擇度量標(biāo)準(zhǔn)6.1概述¡ 路由測度（routing metric）用來在所有可能的路由中確定一條最佳路由。¡ 路由測度的設(shè)計要根據(jù)目標(biāo)網(wǎng)絡(luò)的特性決定，WMN路由測度的設(shè)計要考慮以下兩方面的因素：l 所使用的路由協(xié)議：哪一類路由協(xié)議適合WMN，路由測度的設(shè)計應(yīng)與路由協(xié)議相符合；l Mesh網(wǎng)絡(luò)的特性：靜止節(jié)點 + 共享無線介質(zhì)，有效的路由測度應(yīng)考慮鏈路的信道分配，反映出干擾對路徑性能的影響。 Mesh節(jié)點之間及mesh節(jié)點與網(wǎng)關(guān)之間的通信需要路由協(xié)議支持，路由測度用來在所有可能的路由中確定一條最佳的。路由測度的設(shè)計要根據(jù)目標(biāo)網(wǎng)絡(luò)的特性決定，比如，能量嚴(yán)重

2、受限的傳感器網(wǎng)絡(luò)要求能量有效的路由設(shè)計，移動自組網(wǎng)由于節(jié)點移動要求能有效維護連接的路由協(xié)議。無線mesh網(wǎng)絡(luò)中靜止節(jié)點和共享無線媒體的結(jié)合對于路由測度的設(shè)計提出了特殊的要求。 Mesh網(wǎng)絡(luò)路由測度的設(shè)計要考慮以下兩方面的因素：所使用的路由協(xié)議和mesh網(wǎng)絡(luò)的特性。由于不同的路由協(xié)議產(chǎn)生的代價（消息開銷和管理復(fù)雜性）不同，理解哪一類路由協(xié)議適合于mesh網(wǎng)絡(luò)是很重要的，這樣可使路由測度的設(shè)計與路由協(xié)議相符合。其次，mesh網(wǎng)絡(luò)的特性（節(jié)點靜止，媒體共享）也對路由測度的設(shè)計提出挑戰(zhàn)。比如，由于無線媒體的共享特性，無線鏈路的帶寬不是專用的，鄰居節(jié)點的傳輸會競爭同一個帶寬，因此路由測度要能反映出競爭流

3、之間的干擾。更復(fù)雜的是，由于當(dāng)前的無線網(wǎng)卡可以被配置到不同的信道上，這樣配置到不同信道上的無線鏈路可能不會相互干擾，哪怕它們在物理位置上離得很近。有效的路由測度必須考慮鏈路的信道分配，反映出干擾對路徑性能的影響。6.2無線Mesh 網(wǎng)絡(luò)中的路由選擇度量標(biāo)準(zhǔn)無線Mesh網(wǎng)絡(luò)路由技術(shù)的研究是熱門方向現(xiàn)有的路由協(xié)議均以最小跳數(shù)(HOP)為標(biāo)準(zhǔn)來選擇路由路徑。研究表明跚，該種判據(jù)在大多數(shù)情況下并非有效，如鏈路質(zhì)量較差或網(wǎng)絡(luò)擁擠的情況下，選出的路由往往不是最優(yōu)路由。當(dāng)節(jié)點增加減少或移動時，無線鏈路失效經(jīng)常發(fā)生，何況在無線傳播的情況下，鏈路本身就沒有很好的定義，介質(zhì)共享也帶來了干擾，造成帶寬及鏈路質(zhì)量的不

4、穩(wěn)定。所以，在無線Mesh網(wǎng)絡(luò)的拓撲結(jié)構(gòu)發(fā)生變化時，路由選擇問題變得更加復(fù)雜。傳統(tǒng)的基于因特網(wǎng)的路由協(xié)議以及Ad Hoc網(wǎng)絡(luò)的路由技術(shù)都無法適應(yīng)這些特性，需要有適用于無線Mesh網(wǎng)絡(luò)的專用路由技術(shù)。路由協(xié)議對不同鏈路如何進行權(quán)值的衡量，即采用什么樣的判據(jù)是路由協(xié)議的核心問題之一。近幾年，關(guān)于這方面的研究比較多，分別以網(wǎng)絡(luò)拓撲、鏈路質(zhì)量及負載均衡、流量干擾等為切入點，設(shè)計出了不同的判據(jù)，對網(wǎng)絡(luò)性能有不同程度的提高。文獻24】對幾種典型路由判據(jù)(期望傳輸次數(shù)ETX、往返時間RTT、數(shù)據(jù)對延遲時間PktPair)與HOP進行了比較，當(dāng)節(jié)點完全靜止時，ETX的性能最好，RTT與PktPair由于沖突的

5、影響性能稍差，但是當(dāng)網(wǎng)絡(luò)中節(jié)點移動時，HOP則優(yōu)于其他3種判據(jù)。同時，單一的路由判據(jù)往往很難反映出鏈路質(zhì)量給各個性能指標(biāo)帶來的影響，多路由判據(jù)仍有待研究開發(fā)，區(qū)分無線Mesh網(wǎng)絡(luò)兩類不同節(jié)點的路由判據(jù)研究成果則相對較少。6.2.1跳數(shù)¡ 跳數(shù)反映了路徑長度對流性能的影響。¡ 跳數(shù)測度是保序的，存在有效的算法能夠找到最小跳數(shù)的無環(huán)路徑。跳數(shù)測度沒有考慮不同無線鏈路上傳輸速率和丟包率的差異以及網(wǎng)絡(luò)中的干擾，在WMN中不能獲得良好的性能。跳數(shù)是現(xiàn)有路由協(xié)議最廣泛使用的路由判據(jù)。跳數(shù)反映了路徑長度對數(shù)據(jù)流性能的影響。使用該判據(jù)的路由協(xié)議即最短路由協(xié)議。該判據(jù)所對應(yīng)的鏈路質(zhì)量是一個二

6、態(tài)概念，只有存在與不存在的區(qū)別。該判據(jù)實現(xiàn)簡單，一旦告知網(wǎng)絡(luò)拓撲，很容易計算出源節(jié)點到目的節(jié)點之間的最小跳數(shù)；和其他判據(jù)不同的是，它不需要任何附加測量操作，因而給網(wǎng)絡(luò)帶來的開銷小；在移動的環(huán)境下，跳數(shù)判據(jù)能夠很快適應(yīng)網(wǎng)絡(luò)拓撲的變化；由于跳數(shù)是保序的，有效的算法能夠根據(jù)最小跳數(shù)來發(fā)現(xiàn)無環(huán)路的路由該判據(jù)主要的缺點是沒有考慮丟包率和帶寬因素，也沒有考慮到鏈路負載、網(wǎng)絡(luò)中的干擾等情況。因為可能包括了遠距離低速的鏈路，從而吞吐量比較差。例如有兩條路徑，第一條為可靠或高速的兩跳路徑，第二條為易斷或低速的一跳路徑，前者可能比后者有更好的性能，但使用HOP為判據(jù)時，將選擇后者。6.2.2每跳往返時間該判據(jù)利用

7、鄰居間發(fā)送的單播探測包來對往返時間進行測試。為了計算RTT值，節(jié)點每500ms發(fā)送一個攜帶時間標(biāo)記的單播探測包給鄰節(jié)點，鄰節(jié)點收到該探測包后，立即進行回復(fù)，并把探測包中的時間標(biāo)記回送給源節(jié)點。通過該方法，發(fā)送節(jié)點可以獲得與不同鄰居的往返時間。該節(jié)點利用一個指數(shù)權(quán)重來獲取到達鄰居RTT的平均值，即RTT的加權(quán)平均值。計算平均值時，當(dāng)前采樣值占10，如果探測包或者探測回復(fù)丟失，該比例擴大為20；如果數(shù)據(jù)包丟失，將采取同樣的策略。路由算法選擇所有RTT之和最小的路徑。RTT值體現(xiàn)了網(wǎng)絡(luò)負載、干擾、鏈路丟包率等質(zhì)量因子的變化，可以避免使用高負載與不穩(wěn)定的連接。其缺點是：首先，RTT是一個隨著負載變化而

8、變化的判據(jù)，容易引起路由的不穩(wěn)定；其次，由于要為網(wǎng)絡(luò)中每一對節(jié)點計算R，rr值，對于密集型網(wǎng)絡(luò)，開銷非常大；第三，探測包相對較小，沒有考慮到傳輸速率的影響；若使用較大的探測包放大數(shù)據(jù)傳輸速率影響，又將帶來很大開銷；第四，在接收節(jié)點考慮到隊列延時，在單向傳輸中不能算是正確的度量。該判據(jù)不適合大密度網(wǎng)絡(luò)。6.2.3每跳分組對延遲該判據(jù)是通過發(fā)往某鄰居的一對連續(xù)探側(cè)包的分析統(tǒng)計來獲得的。該設(shè)計可以避免RTT 因隊列延時而產(chǎn)生的失真 為了計算該判據(jù)，節(jié)點需要每2 秒發(fā)送一對探測包給鄰節(jié)點。第一個探側(cè)包較小，第二個較大。鄰居節(jié)點接收數(shù)據(jù)包，計算其時間差，并將該信息回送給源節(jié)點。發(fā)送節(jié)點為每個鄰居維護一個

9、指數(shù)權(quán)重的滑動平均延時。此類路由算法的目標(biāo)是選擇延時之和的最小的路徑與RTT 相似，該判據(jù)反映了丟包率、帶寬、及網(wǎng)絡(luò)中干擾的變化。該判據(jù)與又口相比主要優(yōu)點是不受隊列延時的影響，自干擾比RTT 帶來的自干擾問題小了很多；另外，第二個探測包較大，使得該判據(jù)比RTT 對鏈路帶寬更敏感。該判據(jù)也有自己的缺點：首先，其開銷遠遠大于RTT 判據(jù)，因為鄰居間需要發(fā)送兩個探測包，并且第二個探側(cè)包比較大；其次，該判據(jù)不能完全解決自干擾的問題。6.2.4量化分組丟失率6.2.5預(yù)期傳輸次數(shù)¡ ETX定義為在無線鏈路上成功傳輸一個數(shù)據(jù)包所需要的MAC層傳輸次數(shù)的期望值。¡ 路徑的權(quán)重定義為該路徑

10、上所有鏈路的ETX總和。¡ 由于長路徑和易損路徑具有較大的權(quán)重，因此ETX測度反映了路徑長度和包丟失率的影響。¡ ETX是保序的。ETX沒有考慮干擾以及鏈路速率的影響De Couto等人提出了ETX(ETX，Expected Transmission Count)路由判據(jù)，定義其為MAC層通過一條無線鏈路成功交付一個數(shù)據(jù)包所需期望傳輸次數(shù)。通過在鏈路層發(fā)送廣播包的方法，對ETX進行估計。路徑的權(quán)重定義為路徑上所有鏈路的ETX的總和，協(xié)議應(yīng)選擇具有最小ETX的路徑。假設(shè)P表示x到Y(jié)的丟包率，當(dāng)數(shù)據(jù)包傳輸失敗后，80211將進行重傳。假設(shè)數(shù)據(jù)包經(jīng)過k次重傳后，成功地從x發(fā)送到Y(jié)

11、，則成功傳輸率為：最后成功地把一個數(shù)據(jù)包從x傳輸?shù)結(jié)的期望傳輸次數(shù)為：該判據(jù)通過測試節(jié)點間廣播數(shù)據(jù)包的丟包率來估計單播數(shù)據(jù)包的傳輸次數(shù)。為了計算ETX值，節(jié)點每秒廣播一個探測包，該探測包包括在前10s內(nèi)從鄰居接收到的探測包情況。基于探測包，節(jié)點能分別計算出本節(jié)點到鄰節(jié)點和鄰節(jié)點到本節(jié)點鏈路的探測包丟包率。對于8021lMAC協(xié)議，因為不對廣播包進行重傳，節(jié)點可以運用這些信息估算出ARQ機制對單播數(shù)據(jù)包的重傳次數(shù)。ETX有很多優(yōu)點。首先，ETX判據(jù)捕捉到了數(shù)據(jù)包丟失率和路徑長度的影響；其次，ETX也具備保序性：第三，節(jié)點以廣播包代替以往的單播包，在很大程度上減小了網(wǎng)絡(luò)開銷；最后，該判據(jù)由于沒有考

12、慮延時，所以幾乎沒有白干擾現(xiàn)象發(fā)生。ETX相比于RTT和PktPair而言對負載的敏感度最低。該判據(jù)的主要缺點是并沒有直接考慮鏈路負載和數(shù)據(jù)傳輸速率，也沒有考慮到干擾的存在。6.3改進預(yù)期傳輸次數(shù)雖然ETX比最小跳數(shù)判據(jù)的性能提高了不少，但由于它用平均丟包率來決定路由，不能很好地處理短期信道變化。比如說，也許無線信道的平均丟包率比較低，但是易變，使用平均丟包率為判據(jù)性能就會比較差，因為這樣的信道不能適應(yīng)處理突發(fā)損失的情況。一個路由判據(jù)因此必須同時考慮平均(ETX)和信道的變化性。ETX的改進版mETXt，修正了這個缺點。mETX定義為：椰包含兩部分，µ和2，分別表示了錯誤率的平均狀況

13、和變化性的情況。前者體現(xiàn)一段比較長的時間內(nèi)的信道誤比特率的平均值，111巳似隨著它的增加而增加。后者體現(xiàn)了瞬時傳輸次數(shù)逐包的(packetto-packet)變化性。因此，通過n正，可以區(qū)分在一個數(shù)據(jù)包時間度上變化率不同的信道。與ETX類似，mETX在連續(xù)的鏈路中是可加的。因此，只要簡單地將ETX換成mETX就可以使用那些為ETX所設(shè)計的路由協(xié)議。該判據(jù)也有著與ETX相似的缺點，沒有考慮到傳輸速率、鏈路負載及干擾的影響。6.4有效傳輸數(shù)量通常鏈路層協(xié)議在重傳次數(shù)超過門限值后將自動放棄。如果考慮到最優(yōu)化總吞吐量，即對高層協(xié)議如TCP可見的丟包率進行限制，選擇最大化鏈路層吞吐量的路徑是不夠的，因為

14、其中可能包括高丟包率的鏈路。ENT嗍判據(jù)可以解決這一問題。對無線鏈路，定義：ENT的結(jié)構(gòu)跟mETX類似。主要的區(qū)別是附加了由因子26帶來的自由度。事實上，當(dāng)=-14時，mETX和ENT相等。µ項表示了信道參數(shù)中緩慢變化及靜態(tài)的部分，2項則代表了信道條件在一個數(shù)據(jù)包時間范圍內(nèi)變化相對較快的部分的影響。(3-4)式綜合體現(xiàn)出兩個因素的影響。某種意義上說，利用高層損耗率要求的概念，ENT將兩者映射到同一量綱上，將兩者之和與IogM相比較。如果將發(fā)生丟包之前的最大重傳次數(shù)M定義為“資源"，如果高層覺察到數(shù)據(jù)包丟失，就意味著鏈路層最大重傳次數(shù)M已經(jīng)被用完。ENT主要考慮傳輸次數(shù)超過一定門限值的概率。假設(shè)高層協(xié)議對損耗概率沒有約束，也就是說=0，條件就轉(zhuǎn)化為µ(信道的平均誤