無線Mesh網(wǎng)絡(luò)中網(wǎng)絡(luò)編碼感知路由技術(shù)研究

譚會君 左曉靜

（漯河職業(yè)技術(shù)學(xué)院 信息工程系，河南 漯河 462002）

無線Mesh網(wǎng)絡(luò)中網(wǎng)絡(luò)編碼感知路由技術(shù)研究

譚會君 左曉靜

（漯河職業(yè)技術(shù)學(xué)院 信息工程系，河南 漯河 462002）

隨著計算機網(wǎng)絡(luò)日新月異的發(fā)展，網(wǎng)絡(luò)的傳輸方式已經(jīng)從有線網(wǎng)絡(luò)發(fā)展到無線網(wǎng)絡(luò)，網(wǎng)絡(luò)編碼的出現(xiàn)加快了網(wǎng)絡(luò)發(fā)展的速度，更是將通信網(wǎng)絡(luò)中的信息傳輸方式徹底改變。由于無線網(wǎng)絡(luò)物理層的廣播特性，因此比有線網(wǎng)絡(luò)更適合用于編碼。無線網(wǎng)絡(luò)的吞吐量通過將無線信道的廣播特征和網(wǎng)絡(luò)編碼結(jié)合運用就可以得到提高，也因此網(wǎng)絡(luò)編碼是無線網(wǎng)絡(luò)中的重點組成部分，具有重要的研究價值。

無線Mesh網(wǎng)絡(luò)；網(wǎng)絡(luò)編碼；路由

一、無線Mesh網(wǎng)絡(luò)路由技術(shù)分類概述

無線Mesh網(wǎng)絡(luò)路由以路由建立的方式為依據(jù)，將其分為了五大類，即基于網(wǎng)絡(luò)編碼的路由、機會路由、反應(yīng)式路由、先應(yīng)式路由和混合路由。［1］

（一）先應(yīng)式路由簡述

先應(yīng)式路由包括目的序列距離矢量路由、優(yōu)化鏈路狀態(tài)路由和無線路由協(xié)議等。即表驅(qū)動路由，使用先應(yīng)式路由，網(wǎng)絡(luò)世界里所有節(jié)點的路勁信息都可以被每個節(jié)點維護(hù)的表格所記錄。在網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時可以通過某一節(jié)點向其他節(jié)點發(fā)送信息，促使其他節(jié)點收到信息后可以及時準(zhǔn)確地更新節(jié)點中表格內(nèi)容。但由于先應(yīng)式路由并不是單一的，因此網(wǎng)絡(luò)中對于經(jīng)由先應(yīng)式路由傳播的拓?fù)涓滦畔⒌膫鬏敺绞健⒋鎯π畔⒌谋砀耦愋图案袷蕉即嬖谥鄻有?。先?yīng)式路由的優(yōu)點在于源節(jié)點發(fā)送數(shù)據(jù)時能選擇傳輸最快速的路徑，其原因在于先應(yīng)式路由并不考慮網(wǎng)絡(luò)中的業(yè)務(wù)流量因素，導(dǎo)致資源耗費過大。

（二）反應(yīng)式路由簡述

常見的反應(yīng)式路由有按需距離矢量路由AODV路由、動態(tài)源路由和動態(tài)按需路由。反應(yīng)式路由不同于先應(yīng)式路由，需要一直開啟大量的傳輸路徑保持最快速的數(shù)據(jù)傳輸速度，它只有在需要發(fā)送數(shù)據(jù)時才會啟動相關(guān)的路由發(fā)現(xiàn)進(jìn)程，因此不會給網(wǎng)絡(luò)帶來承重的負(fù)擔(dān)，還因此具備節(jié)能的優(yōu)點。但同時也由于反應(yīng)式路由運作的特點，其缺點在于路由建立時需要花費不必要的時間，拉長了數(shù)據(jù)發(fā)送的時間長度。

（三）混合路由簡述

常見的混合路由有區(qū)域路由協(xié)議、Mesh路由協(xié)議和混合無線Mesh路由等。由于先應(yīng)式路由和反應(yīng)式路由都有其明顯的優(yōu)勢和劣勢，因此混合路由是作為綜合了它們優(yōu)勢的存在，多用于分簇和分區(qū)域的無線Mseh網(wǎng)絡(luò)。鑒于簇間和簇內(nèi)的數(shù)據(jù)傳輸頻繁發(fā)生，為了更好地進(jìn)行數(shù)據(jù)發(fā)送，混合路由多是采用先應(yīng)式路由進(jìn)行簇內(nèi)數(shù)據(jù)傳輸，而簇間數(shù)據(jù)傳輸則采用反應(yīng)式路由的方式。

（四）機會路由簡述

典型的機會路由有ROMER、ExOR和SOAR。而前文所介紹的先應(yīng)式路由、反應(yīng)式路由和混合路由因其在數(shù)據(jù)發(fā)送的全過程中一直按照既定路徑進(jìn)行傳輸，因而被稱作確定性路由。鑒于確定性路由數(shù)據(jù)發(fā)送過程中的既定原則，Biswas等人提出的機會路由的概念，創(chuàng)新了數(shù)據(jù)在節(jié)點中傳播路徑的最優(yōu)選擇方式，路由性能也得到了有效的提升。但時下路由性能仍然受到其下跳節(jié)點復(fù)雜的選擇機制所影響，因而影響了路由性能的全面發(fā)揮。

（五）基于網(wǎng)絡(luò)編碼的路由簡述

典型的基于網(wǎng)絡(luò)編碼的路由主要有MORE、COPE和DCAR等，其運作原理是將路由與網(wǎng)絡(luò)編碼結(jié)合后，通過將網(wǎng)絡(luò)吞吐量提高和數(shù)據(jù)傳輸次數(shù)的減少進(jìn)行運作，并將路由協(xié)議的性能提高?；诰W(wǎng)絡(luò)編碼的路由技術(shù)是本文的重點研究內(nèi)容之一，將在下文展開詳細(xì)論述，故而此處暫且不提。

二、無線Mesh網(wǎng)絡(luò)路由度量

有線網(wǎng)絡(luò)中的鏈路因為具有高質(zhì)量、受干擾較少和較少丟失數(shù)據(jù)的優(yōu)點，常以單跳往返時間、單跳包對延時和跳數(shù)作為路由度量，并以此作為評價路徑和鏈路性能的依據(jù)。與有線網(wǎng)絡(luò)具有高度穩(wěn)定性不同的無線網(wǎng)絡(luò)，因時變性是無線信號的特性以及無線信道的開放性，使得數(shù)據(jù)在傳輸中使用的節(jié)點不僅容易被干擾，而且信號質(zhì)量無法達(dá)到長期穩(wěn)定的狀態(tài)，因此使用無線網(wǎng)絡(luò)傳輸數(shù)據(jù)時無線鏈路的分組時常出現(xiàn)丟失。

（一）跳數(shù)選擇

Mesh網(wǎng)絡(luò)中跳數(shù)相對較大的路徑可以降低丟包率，還能縮短單跳鏈路的距離，因而能夠提高路徑的性能。但跳數(shù)在路由度量中沒有考慮到節(jié)點帶寬是一大缺陷，應(yīng)該給予改良。以HOP度量為例，該路由度量具有操作簡便的優(yōu)點，適合用于拓?fù)漕l繁變換的Ad boc網(wǎng)絡(luò)和有線網(wǎng)絡(luò)。HOP度量是通過計算經(jīng)過路徑上的所有節(jié)點從而選擇出最小的路徑作為路由，但也因此，HOP度量應(yīng)用在無線Mesh網(wǎng)絡(luò)中會降低其性能。

（二）采用RTT值計算單跳往返時間

相鄰節(jié)點間的單播數(shù)據(jù)包的往返時間可以使用RTT進(jìn)行計算［2］，計算RTT值需要在源節(jié)點處以周期性向鄰居節(jié)點發(fā)送攜帶時間信息的單播探測報文；而鄰居節(jié)點則需在收到攜帶時間信息的探測報文的第一時間里向發(fā)送節(jié)點返回，從而計算它們之間的RTT值。節(jié)點的RTT值使用指數(shù)加權(quán)的方法計算是為了保證RTT值的穩(wěn)定性。RTT值的計算存在著一定的缺陷，其一是計算時占用一定的網(wǎng)絡(luò)開銷；其二是節(jié)點的傳輸速率沒有被考慮；其三是由于獨立于負(fù)載的計算會引起網(wǎng)絡(luò)不穩(wěn)，形成自干擾現(xiàn)象。

（三）單跳包對延時

單跳包對延時指的是發(fā)送節(jié)點每隔一段時間向相鄰節(jié)點發(fā)送一對連續(xù)探測包所需要的時間。一般來說，發(fā)送節(jié)點所發(fā)送的探測包第一個要比第二個小，等它們到達(dá)后，由鄰居節(jié)點計算完所需的時間差，再使其返回發(fā)送節(jié)點，計算的方法一般是采用指數(shù)加權(quán)方法，目的是為了提高計算的精確度，并且選擇作為路由的是單挑報對延時和的最小路徑。因為單跳包對延時中兩節(jié)點經(jīng)歷的隊列延時相同，因此隊列延時不會對其造成影響。因為單挑包對延時的開銷不低，因此能夠具有較好的鏈路傳輸速率和帶寬，但仍然時不時地出現(xiàn)自干擾的問題。

（四）ETX與期望傳輸次數(shù)

ETX值的計算需要通過在鏈路層發(fā)送單播包才能準(zhǔn)確計算［3］，同時802.11協(xié)議是ETX值計算所采用的。當(dāng)鄰居節(jié)點收到數(shù)據(jù)包后進(jìn)行回復(fù)，使得發(fā)送節(jié)點收到回復(fù)報文，即代表這個數(shù)據(jù)包完成了一次成功傳輸過程。據(jù)此做一個假設(shè)：鄰居節(jié)點無法接收發(fā)送節(jié)點的失敗概率假設(shè)為pf，而發(fā)送節(jié)點無法接收到接收節(jié)點回復(fù)的傳輸失敗率假設(shè)為pr，以及發(fā)送節(jié)點到接收節(jié)點的丟包率假設(shè)為pf，則存在：

由于數(shù)據(jù)傳輸存在一定的失敗率，因此將發(fā)送節(jié)點進(jìn)行重新傳輸?shù)拇螖?shù)假設(shè)為k，則數(shù)據(jù)成功傳輸?shù)母怕适牵?/p>

也因此進(jìn)行ETX計算時可以得出所需要的期望傳輸次數(shù)，即數(shù)據(jù)包成功從發(fā)送節(jié)點傳輸?shù)?/p>

節(jié)點之所以周期性發(fā)送包含了從前在鄰居節(jié)點得到的反饋信息的廣播探測包，目的就是為了能夠更精確計算出ETX值，并且ETX值和正、反鏈路的丟包率都可以以廣播探測包為基礎(chǔ)進(jìn)行計算。使用ETX計算由于不考慮延時，所以不會出現(xiàn)自干擾現(xiàn)象；但由于探測包小、發(fā)送速率小，以及數(shù)據(jù)傳輸速率和鏈路負(fù)載等因素不被ETX考慮在內(nèi)，因此實際計算得到的鏈路丟包率并不完全貼合實際的網(wǎng)絡(luò)情況。

（五）期望傳輸時間

Draves等針對傳輸速率和鏈路帶寬沒有被ETX考慮在內(nèi)的情況，提出了路由度量ETT，即數(shù)據(jù)包成功在鏈路中傳輸?shù)钠谕麄鬏敃r間，并由此進(jìn)行假設(shè)ETT的計算公式：數(shù)據(jù)包大小假設(shè)為S、鏈路帶寬假設(shè)為B，則有下列公式：

（六）加權(quán)累積期望

路由度量里，WCETT在傳輸數(shù)據(jù)包時考慮到了多接口和多信道的無線路由，因而做出了以下的假設(shè)公式：

WCETT主要包括路徑的ETT值和干擾情況。由此得出了下列公式，而且［0，1］是其取值區(qū)間，調(diào)節(jié)因子是參數(shù)刀。

公式（2-6）反應(yīng)的是前后鏈路在路徑中存在的干擾狀況計算公式。多接口多信道的無線網(wǎng)絡(luò)為了避免出現(xiàn)前后鏈路形成自干擾現(xiàn)象，多會采用一條路徑上的鏈路使用不同信道的方式，即鏈路ETT值的和在使用信道時最小，對鏈路的干擾狀況則會處于最小的概率。

三、網(wǎng)絡(luò)編碼技術(shù)在路由算法中的優(yōu)勢

通過結(jié)合網(wǎng)絡(luò)編碼技術(shù)的原理進(jìn)行路由計算，網(wǎng)絡(luò)編碼的優(yōu)勢主要體現(xiàn)在網(wǎng)絡(luò)吞吐量、網(wǎng)絡(luò)負(fù)載、帶寬、數(shù)據(jù)傳輸次數(shù)，以及網(wǎng)絡(luò)傳輸?shù)目煽啃院桶踩浴?/p>

（一）基于網(wǎng)絡(luò)編碼提高網(wǎng)絡(luò)吞吐量

為了解決傳播速率在實際上無法達(dá)到最大速率最小割的理論上界，因此提出了網(wǎng)絡(luò)編碼，使得一個數(shù)據(jù)包在傳輸時，里邊可以包含多個數(shù)據(jù)包的內(nèi)容，從而有效地提高了網(wǎng)絡(luò)吞吐量。根據(jù)網(wǎng)絡(luò)吞吐量的實質(zhì)，假設(shè)單位容量在網(wǎng)絡(luò)中所有鏈路里都存在，則源節(jié)點有限域空間的大小假設(shè)為|F（q）|，網(wǎng)絡(luò)中節(jié)點數(shù)目假設(shè)為|V|，則通過使用網(wǎng)絡(luò)編碼的組播理論吞吐量是組播路由的網(wǎng)絡(luò)吞吐量的|F（q）|（log|V|）倍。

（二）基于網(wǎng)絡(luò)均衡的網(wǎng)絡(luò)負(fù)載

路由算法使用網(wǎng)絡(luò)編碼后，網(wǎng)絡(luò)中的數(shù)據(jù)流量能夠更大范圍地得到流通，組播傳輸?shù)牧髁糠植疾辉俅讼碎L，疏通了網(wǎng)絡(luò)的使用狀況，減少了干擾堵塞的情況出現(xiàn)，從而均衡了網(wǎng)絡(luò)負(fù)載。

（三）單一數(shù)據(jù)傳輸多重信息量，節(jié)省帶寬消耗并提高利用率

基于網(wǎng)絡(luò)編碼進(jìn)行數(shù)據(jù)傳輸，可以在一個數(shù)據(jù)包里包含多個數(shù)據(jù)包的信息量，減少了反復(fù)使用節(jié)點的頻率，從而減少了帶寬的消耗并提高了其利用率。

（四）數(shù)據(jù)傳輸次數(shù)少，效率提高

自從數(shù)據(jù)傳輸使用了網(wǎng)絡(luò)編碼以后，尤其是在無線網(wǎng)絡(luò)環(huán)境之中，數(shù)據(jù)包傳輸時不僅可以一次性增加傳輸?shù)男畔?nèi)容，同時還能減少多次往返的傳輸次數(shù)，因此可以盡可能地避免出現(xiàn)網(wǎng)絡(luò)干擾現(xiàn)象，使得傳輸效率得以有效提高。

（五）可靠性提高

數(shù)據(jù)包傳輸在使用網(wǎng)絡(luò)編碼后，因其數(shù)據(jù)包內(nèi)包含多個原始數(shù)據(jù)包的信息，因此不需要像往常一樣由于在傳輸過程中發(fā)生了數(shù)據(jù)包丟失的事情而需要源節(jié)點進(jìn)行數(shù)據(jù)包重新傳輸?；诰W(wǎng)絡(luò)編碼進(jìn)行數(shù)據(jù)傳輸增加了傳輸?shù)目煽啃浴?/p>

（六）提高網(wǎng)絡(luò)安全性

使用網(wǎng)絡(luò)編碼進(jìn)行多個數(shù)據(jù)包同時傳輸，使得監(jiān)聽者在解密的過程中尤為困難，也因此可以保證數(shù)據(jù)傳輸時的安全性。

綜上所述，無線Mesh網(wǎng)絡(luò)中使用基于網(wǎng)絡(luò)編碼的感知路由可以進(jìn)一步地推動網(wǎng)絡(luò)安全平穩(wěn)發(fā)展。但由于目前編碼感知路由的研究多處于理論階段，實際運用在網(wǎng)絡(luò)世界的仍然比較少，因此還不能完全發(fā)揮網(wǎng)絡(luò)編碼在無線Mesh網(wǎng)絡(luò)中的真正優(yōu)勢。本文就無線Mesh網(wǎng)絡(luò)編碼感知路由技術(shù)進(jìn)行研究探討，希望能夠起到對該技術(shù)的推廣作用。

［1］熊志強，黃家慶，劉威.無線網(wǎng)絡(luò)編碼綜述［J］.計算機科學(xué)，2007，4（1）：6-10.

［2］董贊強，沈蘇彬.網(wǎng)絡(luò)編碼研究綜述［J］.南京郵電大學(xué)學(xué)報（自然科學(xué)版），2012，（3）：66-75.

［3］張勇，郭達(dá).無線網(wǎng)狀網(wǎng)原理與技術(shù)［M］.北京：電了工業(yè)出版社，2007：7-12.

TN929.5

A

1671-2862（2017）03-0097-03

2017-02-26

本文系2016年度河南省教育廳課題“發(fā)達(dá)國家教師教育制度對我省的借鑒與相關(guān)比較研究”（課題編號：2016-JSJYYB-193）的研究成果。

譚會君，女，河南漯河人，碩士研究生，漯河職業(yè)技術(shù)學(xué)院講師，研究方向：網(wǎng)絡(luò)技術(shù)；左曉靜，女，河南漯河人，漯河職業(yè)技術(shù)學(xué)院講師，研究方向：網(wǎng)絡(luò)技術(shù)。