譚會君 左曉靜

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

無線Mesh網絡中網絡編碼感知路由技術研究

譚會君 左曉靜

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

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

無線Mesh網絡；網絡編碼；路由

一、無線Mesh網絡路由技術分類概述

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

（一）先應式路由簡述

先應式路由包括目的序列距離矢量路由、優(yōu)化鏈路狀態(tài)路由和無線路由協(xié)議等。即表驅動路由，使用先應式路由，網絡世界里所有節(jié)點的路勁信息都可以被每個節(jié)點維護的表格所記錄。在網絡拓撲發(fā)生變化時可以通過某一節(jié)點向其他節(jié)點發(fā)送信息，促使其他節(jié)點收到信息后可以及時準確地更新節(jié)點中表格內容。但由于先應式路由并不是單一的，因此網絡中對于經由先應式路由傳播的拓撲更新信息的傳輸方式、存儲信息的表格類型及格式都存在著多樣性。先應式路由的優(yōu)點在于源節(jié)點發(fā)送數(shù)據(jù)時能選擇傳輸最快速的路徑，其原因在于先應式路由并不考慮網絡中的業(yè)務流量因素，導致資源耗費過大。

（二）反應式路由簡述

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

（三）混合路由簡述

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

（四）機會路由簡述

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

（五）基于網絡編碼的路由簡述

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

二、無線Mesh網絡路由度量

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

（一）跳數(shù)選擇

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

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

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

（三）單跳包對延時

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

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

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

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

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

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

（五）期望傳輸時間

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

（六）加權累積期望

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

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

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

三、網絡編碼技術在路由算法中的優(yōu)勢

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

（一）基于網絡編碼提高網絡吞吐量

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

（二）基于網絡均衡的網絡負載

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

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

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

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

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

（五）可靠性提高

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

（六）提高網絡安全性

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

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

［1］熊志強，黃家慶，劉威.無線網絡編碼綜述［J］.計算機科學，2007，4（1）：6-10.

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

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

TN929.5

A

1671-2862（2017）03-0097-03

2017-02-26

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

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