譚會(huì)君 左曉靜

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

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

譚會(huì)君 左曉靜

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

隨著計(jì)算機(jī)網(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é)合運(yùn)用就可以得到提高，也因此網(wǎng)絡(luò)編碼是無線網(wǎng)絡(luò)中的重點(diǎn)組成部分，具有重要的研究?jī)r(jià)值。

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

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

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

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

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

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

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

（三）混合路由簡(jiǎn)述

常見的混合路由有區(qū)域路由協(xié)議、Mesh路由協(xié)議和混合無線Mesh路由等。由于先應(yīng)式路由和反應(yīng)式路由都有其明顯的優(yōu)勢(shì)和劣勢(shì)，因此混合路由是作為綜合了它們優(yōu)勢(shì)的存在，多用于分簇和分區(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)式路由的方式。

（四）機(jī)會(huì)路由簡(jiǎn)述

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

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

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

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

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

（一）跳數(shù)選擇

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

（二）采用RTT值計(jì)算單跳往返時(shí)間

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

（三）單跳包對(duì)延時(shí)

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

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

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

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

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

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

（五）期望傳輸時(shí)間

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

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

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

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

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

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

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

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

為了解決傳播速率在實(shí)際上無法達(dá)到最大速率最小割的理論上界，因此提出了網(wǎng)絡(luò)編碼，使得一個(gè)數(shù)據(jù)包在傳輸時(shí)，里邊可以包含多個(gè)數(shù)據(jù)包的內(nèi)容，從而有效地提高了網(wǎng)絡(luò)吞吐量。根據(jù)網(wǎng)絡(luò)吞吐量的實(shí)質(zhì)，假設(shè)單位容量在網(wǎng)絡(luò)中所有鏈路里都存在，則源節(jié)點(diǎn)有限域空間的大小假設(shè)為|F（q）|，網(wǎng)絡(luò)中節(jié)點(diǎn)數(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(zhǎng)，疏通了網(wǎng)絡(luò)的使用狀況，減少了干擾堵塞的情況出現(xiàn)，從而均衡了網(wǎng)絡(luò)負(fù)載。

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

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

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

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

（五）可靠性提高

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

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

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

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

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

［2］董贊強(qiáng)，沈蘇彬.網(wǎng)絡(luò)編碼研究綜述［J］.南京郵電大學(xué)學(xué)報(bào)（自然科學(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ó)家教師教育制度對(duì)我省的借鑒與相關(guān)比較研究”（課題編號(hào)：2016-JSJYYB-193）的研究成果。

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