一種基于網(wǎng)絡(luò)編碼的無線網(wǎng)絡(luò)機(jī)會(huì)路由算法*

田賢忠，劉 強(qiáng)，胡同森

(浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310023)

傳統(tǒng)無線自組織網(wǎng)絡(luò)和傳感器網(wǎng)絡(luò)的路由協(xié)議都采用確定性路由［1－3］方式，即:在端到端的數(shù)據(jù)傳輸過程中，首先建立一條端到端的節(jié)點(diǎn)序列，然后在每次分組轉(zhuǎn)發(fā)時(shí)，首先確定一個(gè)下一跳節(jié)點(diǎn)，再執(zhí)行鏈路層轉(zhuǎn)發(fā)。如果傳輸過程中發(fā)生分組丟失或差錯(cuò)，則啟動(dòng)鏈路層重傳。在鏈路質(zhì)量和穩(wěn)定性較差的環(huán)境下，頻繁的鏈路層數(shù)據(jù)重傳將消耗大量的帶寬資源。因此，盡管確定性路由方式邏輯簡單，但未能充分考慮無線信道的廣播特性、時(shí)變特性和干擾不規(guī)則性等特點(diǎn)。無線信道的廣播特性使得一次分組轉(zhuǎn)發(fā)可能被多個(gè)節(jié)點(diǎn)收到，且接收概率各不相同；無線鏈路的時(shí)變特性導(dǎo)致網(wǎng)絡(luò)中鏈路的狀態(tài)隨時(shí)間而改變。路由協(xié)議設(shè)計(jì)過程中如果缺乏對(duì)信道廣播和丟失特性的充分考慮，必將導(dǎo)致大量網(wǎng)絡(luò)資源無謂浪費(fèi)，這將嚴(yán)重影響網(wǎng)絡(luò)的吞吐量及其它性能。

針對(duì)無線信道的廣播、時(shí)變、丟失特性和確定性路由策略的不足，麻省理工學(xué)院(MIT)的Biswas等人于2004年率先提出了機(jī)會(huì)路由［4－5］的概念。機(jī)會(huì)路由通過多個(gè)潛在中繼節(jié)點(diǎn)競爭、自主智能進(jìn)行下一跳節(jié)點(diǎn)選擇。它充分利用了信道廣播特性，提高了網(wǎng)絡(luò)的吞吐量和傳輸可靠性。研究機(jī)會(huì)路由算法［6－8］來提升無線多跳網(wǎng)絡(luò)的性能，已成為當(dāng)前無線自組織網(wǎng)絡(luò)與傳感器網(wǎng)絡(luò)組網(wǎng)協(xié)議研究中的一個(gè)重要方向。

網(wǎng)絡(luò) 編 碼［9－12］(Network Coding) 技 術(shù) 由 R.Ahlswede等人在2000年首次提出的。該技術(shù)可以極大地提高網(wǎng)絡(luò)的吞吐量和可靠性。如何同時(shí)發(fā)揮機(jī)會(huì)路由和網(wǎng)絡(luò)編碼的優(yōu)勢(shì)，文獻(xiàn)［13］中的MORE協(xié)議對(duì)此進(jìn)行了嘗試。MORE是一個(gè)MAC無關(guān)的協(xié)議，它通過引入網(wǎng)絡(luò)編碼解決了數(shù)據(jù)傳輸過程中節(jié)點(diǎn)協(xié)作難的問題，即:轉(zhuǎn)發(fā)節(jié)點(diǎn)可以不管其他節(jié)點(diǎn)發(fā)送的是什么數(shù)據(jù)，而只需要將自己緩存下來的數(shù)據(jù)進(jìn)行編碼后轉(zhuǎn)發(fā)出去即可，目的節(jié)點(diǎn)收到一定數(shù)量的編碼包后解出相應(yīng)的原數(shù)據(jù)包。同時(shí)它充分利用了網(wǎng)絡(luò)的空間關(guān)系，通過多個(gè)節(jié)點(diǎn)的協(xié)作轉(zhuǎn)發(fā)數(shù)據(jù)包，而不是某一個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)。但是它有一個(gè)致命的缺陷就是“停止－等待”機(jī)制，即網(wǎng)絡(luò)中只能存在一段數(shù)據(jù)，源節(jié)點(diǎn)只有收到目的節(jié)點(diǎn)的ACK確認(rèn)信息后才開始發(fā)送下一段數(shù)據(jù)，這樣就影響了網(wǎng)絡(luò)的吞吐量。為此，Lin Y［14－15］等人給出了兩種不同的解決方案:文獻(xiàn)［14］同樣是采用分段的形式傳輸，但能夠同時(shí)傳輸多個(gè)段，效率有一定的提高，但是存在ACK數(shù)量較多的問題，它在一定程度上占用了網(wǎng)絡(luò)帶寬資源；文獻(xiàn)［15］則從另一個(gè)方面入手來解決MORE的問題，它摒棄了段的概念，將數(shù)據(jù)看成一個(gè)很長的流，采用“滑動(dòng)窗口”的形式進(jìn)行傳輸，也在一定程度上解決了MORE的問題。文獻(xiàn)［16］則從另一個(gè)角度發(fā)揮機(jī)會(huì)路由與網(wǎng)絡(luò)編碼的優(yōu)勢(shì)，它用個(gè)一種新的確認(rèn)機(jī)制來壓縮傳統(tǒng)ACK確認(rèn)機(jī)制帶來的開銷，在一定程度上改善了網(wǎng)絡(luò)的性能。

從上面的分析可以看出，提高網(wǎng)絡(luò)的吞吐量需從兩個(gè)方面著手:(1)發(fā)送ACK確認(rèn)信息要及時(shí)；(2)發(fā)的ACK確認(rèn)信息要少。為此，本文提出一種最大限度的壓縮ACK的機(jī)制，我們稱之為MinACK算法。它較為及時(shí)地發(fā)送ACK，從而允許同時(shí)在網(wǎng)絡(luò)中傳輸多個(gè)數(shù)據(jù)段；同時(shí)每發(fā)送一段數(shù)據(jù)只需回一個(gè)ACK，減少了ACK的發(fā)送。另外，它還與MAC無關(guān)，省去了許多節(jié)點(diǎn)之間協(xié)作的開銷，從而進(jìn)一步提高網(wǎng)絡(luò)的吞吐量。我們?cè)诜抡鎸?shí)驗(yàn)中也充分證明了MinACK的優(yōu)勢(shì)所在。

1 MinACK基本思想與算法

如圖1所示，在MORE算法中，源節(jié)點(diǎn)S首先把要發(fā)送的數(shù)據(jù)包分成相同大小的數(shù)據(jù)段，每一數(shù)據(jù)段由K個(gè)數(shù)據(jù)包組成，然后把同一段的K個(gè)數(shù)據(jù)包線性網(wǎng)絡(luò)編碼后發(fā)送。節(jié)點(diǎn)A、B、C在收到源節(jié)點(diǎn)S發(fā)送過來的編碼包后，與各自之前已收到的同一數(shù)據(jù)段的編碼包重新編碼后再發(fā)送。目的節(jié)點(diǎn)D收到K個(gè)線性無關(guān)的編碼包后解出原始數(shù)據(jù)包，并發(fā)送一個(gè)確認(rèn)信息ACK給源節(jié)點(diǎn)S。源節(jié)點(diǎn)S在收到ACK后發(fā)送下一段數(shù)據(jù)包。這樣有一個(gè)問題，目的節(jié)點(diǎn)D在能解碼時(shí)，源節(jié)點(diǎn)S不能馬上發(fā)送下一段的數(shù)據(jù)包，必須等到收到ACK后才開始發(fā)送，這樣造成源節(jié)點(diǎn)S延遲發(fā)送，影響網(wǎng)絡(luò)的吞吐量，在跳數(shù)比較多的情況下，這種影響尤為嚴(yán)重。

圖1 MinACK原理圖

MinACK的基本思想是:當(dāng)源節(jié)點(diǎn)S向下一跳節(jié)點(diǎn)廣播編碼包時(shí)，下一跳節(jié)點(diǎn)A、B、C由于丟包可能各自只收到部分編碼包，但當(dāng)節(jié)點(diǎn)A、B、C總共收到足夠多(大于等于K個(gè))的線性無關(guān)的編碼包后，其中一個(gè)節(jié)點(diǎn)發(fā)送一個(gè)確認(rèn)信息ACK給源節(jié)點(diǎn)。源節(jié)點(diǎn)在收到ACK確認(rèn)信息后馬上可以發(fā)送下一數(shù)據(jù)段的數(shù)據(jù)包。因?yàn)檫@時(shí)節(jié)點(diǎn)A、B、C中含有足夠多的線性無關(guān)編碼包可以發(fā)送給目的節(jié)點(diǎn)D。這樣源節(jié)點(diǎn)不需要等目的節(jié)點(diǎn)發(fā)送ACK，只需下一跳的節(jié)點(diǎn)發(fā)送的ACK，節(jié)省等待時(shí)延。而下一跳的A、B、C三個(gè)節(jié)點(diǎn)中只有一個(gè)節(jié)點(diǎn)在它們收到同一數(shù)據(jù)段的K個(gè)線性無關(guān)編碼包后才發(fā)送一個(gè)ACK，這樣ACK的數(shù)量也會(huì)盡可能的少。

MinACK算法針對(duì)源節(jié)點(diǎn)、中繼節(jié)點(diǎn)和目的節(jié)點(diǎn)分三部分:

(1)源節(jié)點(diǎn)

①源節(jié)點(diǎn)S首先把要發(fā)送的數(shù)據(jù)包分成相同大小的數(shù)據(jù)段，每個(gè)數(shù)據(jù)段由K個(gè)數(shù)據(jù)包組成，然后把同一段的K個(gè)數(shù)據(jù)包線性編碼產(chǎn)生編碼包。當(dāng)源節(jié)點(diǎn)S競爭獲得信道后向下一跳節(jié)點(diǎn)廣播(發(fā)送編碼包的個(gè)數(shù)根據(jù)§2.3確定)。

②當(dāng)源節(jié)點(diǎn)S接收到下一跳節(jié)點(diǎn)的ACK后，發(fā)送下一段的數(shù)據(jù)包。

(2)中繼節(jié)點(diǎn)

①中繼節(jié)點(diǎn)v在收到前一跳節(jié)點(diǎn)u發(fā)送的編碼包后，就與其之前已收到的同一段的編碼包重新編碼后向其下一跳節(jié)點(diǎn)廣播(發(fā)送編碼包的個(gè)數(shù)也根據(jù)§2.3確定)。這時(shí)如果節(jié)點(diǎn)v已收到同一段的K個(gè)編碼包，就向上一跳節(jié)點(diǎn)廣播一個(gè)確認(rèn)信息ACK。

②節(jié)點(diǎn)v向下一跳廣播發(fā)送編碼包時(shí)，其前一跳節(jié)點(diǎn)u的其它下一跳節(jié)點(diǎn)w也收到了，也就是說節(jié)點(diǎn)w不但收到上一跳節(jié)點(diǎn)u的編碼包，也收到同層節(jié)點(diǎn)v的編碼包。不管哪種情況，節(jié)點(diǎn)w對(duì)收到的編碼包也判斷是否與之前收到的同一段的編碼包線性相關(guān)，如果線性無關(guān)就編碼后向其下一跳節(jié)點(diǎn)廣播(發(fā)送編碼包的個(gè)數(shù)也根據(jù)§2.3確定)。同時(shí)判斷如果節(jié)點(diǎn)w收到同一段的編碼包個(gè)數(shù)為K個(gè)，就向上一跳節(jié)點(diǎn)廣播一個(gè)ACK。

③如果節(jié)點(diǎn)u收到的是節(jié)點(diǎn)v向上一跳節(jié)點(diǎn)發(fā)送的確認(rèn)信息ACK，則停止本段編碼包的接收，等待接收下一段編碼包。

(3)目的節(jié)點(diǎn)

目的節(jié)點(diǎn)D在收到K個(gè)編碼包后，解出原始數(shù)據(jù)包，同時(shí)向前一跳節(jié)點(diǎn)發(fā)送確認(rèn)信息ACK。

2 MinACK具體實(shí)現(xiàn)

上面的算法中，有幾個(gè)問題必須明確:(1)如何確定下一跳節(jié)點(diǎn)；(2)編碼解碼策略；(3)節(jié)點(diǎn)轉(zhuǎn)發(fā)編碼包數(shù)目；(4)ACK確認(rèn)包的格式。

2.1 下一跳節(jié)點(diǎn)與上一跳節(jié)點(diǎn)

MinACK算法中節(jié)點(diǎn)v的下一跳節(jié)點(diǎn)是指到目的節(jié)點(diǎn)的ETX［17］值比自己小的鄰居節(jié)點(diǎn)，即Next(v)={u|ETX(u)＜ETX(v)且u∈Neighbour(v)}其中Neighbour(v)表示節(jié)點(diǎn)v的一跳鄰居節(jié)點(diǎn)；同樣，節(jié)點(diǎn)v的上一跳節(jié)點(diǎn)是指到目的節(jié)點(diǎn)的ETX值比自己大的鄰居節(jié)點(diǎn)，即

網(wǎng)絡(luò)中的節(jié)點(diǎn)通過周期性的互相探測(cè)來獲得每條鏈路的成功傳輸率，ETX值是對(duì)應(yīng)鏈路的成功傳輸率的倒數(shù)，表示發(fā)送成功一個(gè)數(shù)據(jù)包平均需要發(fā)送的次數(shù)。節(jié)點(diǎn)到目的節(jié)點(diǎn)的ETX值等于其路徑上每一跳的ETX之和。每個(gè)節(jié)點(diǎn)都計(jì)算并記錄自己到目的節(jié)點(diǎn)的ETX值。根據(jù)ETX值可以找到節(jié)點(diǎn)的下一跳與上一跳節(jié)點(diǎn)。

2.2 編碼解碼策略

編碼包在轉(zhuǎn)發(fā)節(jié)點(diǎn)處被重新編碼，易得重新編碼后的包仍然是原始包的線性組合，因?yàn)?/p>

目的節(jié)點(diǎn)一旦接收到同一段的K個(gè)線性獨(dú)立的編碼包，它就可以用以下方式解碼:

其中PCi'是目的節(jié)點(diǎn)接收的編碼包，Pi是原始包，i=(ci1，…，ciK)是編碼包PC'i對(duì)應(yīng)的編碼向量，通過高斯消元即可解碼出原始包。

2.3 節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的數(shù)目

當(dāng)一個(gè)節(jié)點(diǎn)收到一個(gè)編碼包后，會(huì)觸發(fā)其重新編碼后向下一跳節(jié)點(diǎn)發(fā)送編碼包。那么應(yīng)該發(fā)送多少個(gè)編碼包?按傳統(tǒng)方法每收到一個(gè)發(fā)送一個(gè)會(huì)帶來兩個(gè)問題:①由于丟包，只發(fā)送一個(gè)包下游節(jié)點(diǎn)可能會(huì)收不到；②因?yàn)楣?jié)點(diǎn)是廣播編碼包的，所以可能會(huì)有多個(gè)下一跳節(jié)點(diǎn)收到此編碼包，每個(gè)收到的節(jié)點(diǎn)都發(fā)一個(gè)包會(huì)造成重復(fù)發(fā)送。其實(shí)多個(gè)下一跳節(jié)點(diǎn)中只需要一個(gè)節(jié)點(diǎn)發(fā)送就可以了。

首先考慮源節(jié)點(diǎn)需發(fā)送一個(gè)數(shù)據(jù)包時(shí)，每個(gè)節(jié)點(diǎn)需發(fā)送的數(shù)據(jù)包個(gè)數(shù)。根據(jù)文獻(xiàn)［13］，設(shè)puv表示節(jié)點(diǎn)u到節(jié)點(diǎn)v的丟包率，nu表示節(jié)點(diǎn)u發(fā)送數(shù)據(jù)包的次數(shù)，則節(jié)點(diǎn)v收到編碼包的個(gè)數(shù)為:

實(shí)際操作時(shí)，在每個(gè)節(jié)點(diǎn)v中設(shè)置一個(gè)計(jì)數(shù)器Countv。首選設(shè)Countv=0；每當(dāng)節(jié)點(diǎn)v收到一個(gè)編碼包，則 Countv=Countv+npv；這時(shí)，如果 Countv＞0，節(jié)點(diǎn)v發(fā)送一個(gè)編碼包，同時(shí)Countv=Countv－1。當(dāng)節(jié)點(diǎn)v發(fā)送下一數(shù)據(jù)段時(shí)Countv清零。

2.4 ACK 確認(rèn)包

當(dāng)節(jié)點(diǎn)i知道自己的下一跳節(jié)點(diǎn)中已接收到同一數(shù)據(jù)段的K個(gè)編碼包時(shí)，節(jié)點(diǎn)i就向其上游節(jié)點(diǎn)發(fā)送一個(gè)ACK確認(rèn)信息。上游節(jié)點(diǎn)在收到ACK后刪除緩存中這一段的編碼包，開始發(fā)送下一段數(shù)據(jù)的編碼包。如圖2所示，ACK數(shù)據(jù)包主要包含三個(gè)域:發(fā)送節(jié)點(diǎn)ID是指發(fā)送ACK節(jié)點(diǎn)的編號(hào)，接收節(jié)點(diǎn)ID列表為發(fā)送節(jié)點(diǎn)的上一跳節(jié)點(diǎn)的編號(hào)列表，數(shù)據(jù)段ID告訴接收節(jié)點(diǎn)哪一數(shù)據(jù)段已被其下游節(jié)點(diǎn)收到，可以清除緩存中的這段編碼包。

圖2 ACK包格式

3 性能分析

MinACK能在網(wǎng)絡(luò)中同時(shí)傳輸多個(gè)數(shù)據(jù)段，從而提高網(wǎng)絡(luò)的吞吐量。這里分析網(wǎng)絡(luò)中能同時(shí)傳輸?shù)臄?shù)據(jù)段數(shù)以及網(wǎng)絡(luò)的吞吐量。

3.1 網(wǎng)絡(luò)中能同步傳輸?shù)亩螖?shù)

從MinACK算法中我們可以知道，當(dāng)某個(gè)中繼節(jié)點(diǎn)回了一個(gè)ACK后，其上一跳節(jié)點(diǎn)可以發(fā)送下一數(shù)據(jù)段。我們可以從第二跳節(jié)點(diǎn)(和源節(jié)點(diǎn)直接相連的節(jié)點(diǎn))發(fā)送的ACK數(shù)量來判斷網(wǎng)絡(luò)中同時(shí)傳輸?shù)臄?shù)據(jù)段數(shù):

其中nseg表示網(wǎng)絡(luò)中同時(shí)存在的數(shù)據(jù)段數(shù)，nack表示第二跳節(jié)點(diǎn)回ACK數(shù)量，ndestACK是目的節(jié)點(diǎn)回的ACK數(shù)量。

發(fā)送ACK的數(shù)量nack和ndestACK仿真實(shí)驗(yàn)與實(shí)際傳輸中很容易記錄下來，但理論計(jì)算比較難。我們用另一種思路來計(jì)算網(wǎng)絡(luò)中同時(shí)傳輸?shù)臄?shù)據(jù)段數(shù)。其實(shí)，段數(shù)與傳輸一個(gè)數(shù)據(jù)包的跳數(shù)有關(guān)。如圖3所示，如果數(shù)據(jù)包從源節(jié)點(diǎn)S經(jīng)節(jié)點(diǎn)B發(fā)送給目的節(jié)點(diǎn)D(下面稱“路徑P1”)，只需兩跳。這時(shí)，節(jié)點(diǎn)B收到數(shù)據(jù)包回ACK后，源節(jié)點(diǎn)S可以發(fā)送下一數(shù)據(jù)包，網(wǎng)絡(luò)中存在兩個(gè)數(shù)據(jù)段。如果源節(jié)點(diǎn)S經(jīng)節(jié)點(diǎn)A、B發(fā)送給目的節(jié)點(diǎn)D(下面稱“路徑P2”)，則數(shù)據(jù)包發(fā)送需要三跳。這時(shí)，節(jié)點(diǎn)A、B都可以回ACK，網(wǎng)絡(luò)中同時(shí)存在三段數(shù)據(jù)段。所以數(shù)據(jù)段數(shù)與傳輸一個(gè)數(shù)據(jù)包的跳數(shù)相對(duì)應(yīng)，即

圖3 跳數(shù)與段數(shù)關(guān)系

而傳輸一個(gè)數(shù)據(jù)包的跳數(shù)就是傳輸這個(gè)數(shù)據(jù)包時(shí)各個(gè)節(jié)點(diǎn)所要傳輸?shù)拇螖?shù)之和。如圖3，如果采用“路徑P1”節(jié)點(diǎn)S需傳輸1次，節(jié)點(diǎn)B需傳輸1次，共兩次，與跳數(shù)相等；同樣，如果采用“路徑P2”，節(jié)點(diǎn)S、A、B各傳輸1次，共3次，也與跳數(shù)相等。當(dāng)傳輸一個(gè)數(shù)據(jù)包，采用“路徑P1”和“路徑P2”的概率都為0.5，則平均跳數(shù)為:0.5×2+0.5×3=2.5。而每個(gè)節(jié)點(diǎn)的傳輸次數(shù)分別為S=1，A=0.5，B=1，共2.5次，與平均跳數(shù)相等。

在實(shí)際網(wǎng)絡(luò)中源節(jié)點(diǎn)傳輸一個(gè)數(shù)據(jù)包，節(jié)點(diǎn)v需傳輸?shù)臄?shù)據(jù)包個(gè)數(shù)為Lv，根據(jù)式(2)，可以求出所有節(jié)點(diǎn)的發(fā)送次數(shù)，即網(wǎng)絡(luò)中同時(shí)傳輸?shù)臄?shù)據(jù)段數(shù)為:

3.2 網(wǎng)絡(luò)的吞吐量

網(wǎng)絡(luò)的吞吐量是網(wǎng)絡(luò)性能的一項(xiàng)重要標(biāo)志。假設(shè)一個(gè)數(shù)據(jù)包發(fā)送一次所需時(shí)間為t。這里我們忽略計(jì)算時(shí)間(包括編碼與解碼所需要的時(shí)間)，因?yàn)橛?jì)算時(shí)間比傳輸時(shí)間要小得多，可以忽略不計(jì)。首選計(jì)算目的節(jié)點(diǎn)收到一段數(shù)據(jù)包(K個(gè)編碼包)所需的時(shí)間Ttotal。Ttotal包括兩部分:第一個(gè)編碼包從源節(jié)點(diǎn)傳輸?shù)侥康墓?jié)點(diǎn)的時(shí)延T1和目的節(jié)點(diǎn)從收到第一個(gè)編碼包后到收完其余K－1個(gè)編碼包所用的時(shí)間T2，即:

因?yàn)橐粋€(gè)包從源節(jié)點(diǎn)傳輸?shù)侥康墓?jié)點(diǎn)的時(shí)延為其傳輸次數(shù)×t，同時(shí)考慮MinACK可以在網(wǎng)絡(luò)中同時(shí)傳輸多段數(shù)據(jù)包，得T1值為:

其中ntotal是從源節(jié)點(diǎn)傳輸一個(gè)數(shù)據(jù)包到目的節(jié)點(diǎn)所有節(jié)點(diǎn)傳輸次數(shù)，根據(jù)式(3)，其值為:

根據(jù)式(8)、式(9)、式(11)計(jì)算出Ttotal。

網(wǎng)絡(luò)吞吐量是單位時(shí)間內(nèi)傳輸?shù)臄?shù)據(jù)量。由前面分析可知，傳輸K個(gè)編碼包的時(shí)間為Ttotal，假設(shè)每個(gè)編碼包的大小是M，則吞吐量

4 仿真實(shí)驗(yàn)

本文使用Matlab語言對(duì)MinACK協(xié)議進(jìn)行仿真模擬，以觀察在傳輸相同數(shù)量的數(shù)據(jù)包的情況下ExOR、MORE以及MinACK傳輸次數(shù)，網(wǎng)絡(luò)中存在的段數(shù)以及網(wǎng)絡(luò)的吞吐量等性能。我們?cè)?0 m×50 m的范圍內(nèi)隨機(jī)分布30個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的通信范圍為20 m，節(jié)點(diǎn)之間的傳輸概率是根據(jù)距離大小隨機(jī)產(chǎn)生的(圖4的仿真除外)，每個(gè)數(shù)據(jù)包的大小為M=1000 byte，數(shù)據(jù)包傳輸一次用時(shí)為t=0.1 s。

理論上我們的MinACK和MORE傳輸相同數(shù)量的數(shù)據(jù)包的情況下，他們的傳輸次數(shù)是相同的，圖3、圖4均證明了這一點(diǎn)。我們的優(yōu)勢(shì)主要在于MinACK能夠幾段同步傳輸。圖4我們是通過傳輸50個(gè)包，改變節(jié)點(diǎn)間的傳輸成功率(從0.1到0.9變化)統(tǒng)計(jì)三者的傳輸次數(shù)得到的。從仿真結(jié)果看節(jié)點(diǎn)間的傳輸成功率越低，MinACK和MORE的優(yōu)勢(shì)較之ExOR就越明顯；圖5我們是通過改變傳輸包的個(gè)數(shù)，而節(jié)點(diǎn)間的傳輸概率不變得到的?？傮w上都是隨著數(shù)據(jù)包的增多，傳輸次數(shù)相應(yīng)的平穩(wěn)增加，但在相同條件下MinACK、MORE需要的傳輸次數(shù)比ExOR要少。

圖4 MinACK、MORE和ExOR的傳輸次數(shù)隨節(jié)點(diǎn)間的傳輸成功的概率的變化對(duì)比

圖5 MinACK、MORE和ExOR的傳輸次數(shù)隨傳輸?shù)陌膫€(gè)數(shù)變化對(duì)比

另外，網(wǎng)絡(luò)中多段數(shù)據(jù)包同步傳輸是MinACK協(xié)議的最重要的特征，因此我們對(duì)網(wǎng)絡(luò)中存在的段數(shù)進(jìn)行了仿真測(cè)試。我們將每段數(shù)據(jù)包的個(gè)數(shù)設(shè)為10到100之間，分別測(cè)試網(wǎng)絡(luò)中平均存在的段數(shù)，并與理論值做了對(duì)比，效果如圖6所示，從仿真結(jié)果看，MinACK網(wǎng)絡(luò)中平均存在3段左右的數(shù)據(jù)包在同步發(fā)送，而我們知道MORE網(wǎng)絡(luò)中始終只存在一段數(shù)據(jù)包，因此MinACK應(yīng)該比MORE的吞吐量性能好，接下來的吞吐量仿真也充分證明了這一點(diǎn)。

圖6 MinACK在網(wǎng)絡(luò)中存在的段數(shù)與理論值對(duì)比

最后，吞吐量性能是所有網(wǎng)絡(luò)協(xié)議要考慮的重要特性之一，因此我們也對(duì)吞吐量性能進(jìn)行了仿真實(shí)驗(yàn)，仿真結(jié)果如圖7和圖8所示。

圖7 MinACK、MORE和ExOR的吞吐量隨每段中數(shù)據(jù)包的個(gè)數(shù)變化對(duì)比

圖8 MinACK、MORE和ExOR的吞吐量隨傳輸?shù)陌膫€(gè)數(shù)的變化對(duì)比

圖7是我們通過傳輸500個(gè)數(shù)據(jù)包，讓K(每段中數(shù)據(jù)包的個(gè)數(shù))從10到100之間變化得到的，從仿真結(jié)果看隨著K的增大，三者的吞吐量相差越來越?。粓D8中K固定為50，通過改變傳輸數(shù)據(jù)包的個(gè)數(shù)得到的，從仿真結(jié)果可以看出，三者的吞吐量隨傳輸包的個(gè)數(shù)變化不大。在K較小的新情況下，MORE的吞吐量大概是ExOR的1.2倍左右，MinACK的吞吐量大概是MORE的1.2倍左右，是ExOR的的1.45倍左右，可見吞吐量性能有了不少的提高。

5 小結(jié)

本文提出了一種基于網(wǎng)絡(luò)編碼的機(jī)會(huì)路由算法－MinACK，它結(jié)合了網(wǎng)絡(luò)編碼與機(jī)會(huì)路由的優(yōu)點(diǎn)，通過在網(wǎng)絡(luò)中同時(shí)傳輸多個(gè)數(shù)據(jù)段，提高了網(wǎng)絡(luò)的吞吐量。同時(shí)分析了網(wǎng)絡(luò)中同時(shí)傳輸?shù)臄?shù)據(jù)段數(shù)和網(wǎng)絡(luò)吞吐量等性能。

不同的網(wǎng)絡(luò)中數(shù)據(jù)流有自己的特點(diǎn)，比如數(shù)據(jù)包的到達(dá)服從某種分布。如何利用網(wǎng)絡(luò)編碼，結(jié)合數(shù)據(jù)流的特點(diǎn)定量化地研究無線網(wǎng)絡(luò)的傳輸機(jī)制是作者下一步要研究的內(nèi)容。

［1］程大偉，趙海，張希元，等.基于EWMA的無線傳感器網(wǎng)絡(luò)路由度量性研究［J］.傳感技術(shù)學(xué)報(bào)，2008，21(1):103－108.

［2］Garcia P J，Duato J，F(xiàn)lich J，et al.Cost-Effective Congestionmanagement for Interconnection Networks Using Distributed Deterministic Routing［C］//IEEE，International Conference on，Parallel and Distributed Systems，Univ of Castilla-La Mancha，Albacete，Spain，Dec 2010:355－364.

［3］程遠(yuǎn)國，李國徽.一種面向目標(biāo)跟蹤應(yīng)用的傳感器網(wǎng)絡(luò)路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2008，21(10):1744－1749.

［4］Biswas S，Morris R.Opportunistic Routing in Multi-Hop Wireless Networks［J］.In ACM SIGCOMM Computer ommunications Review，Jan 2004，34(1):69－74.

［5］Biswas S，Morris R.ExOR:Opportunistic Multi-Hop Routing for Wireless Networks［J］.ACM SIGCOMM Computer Communication Review，Aug 2005，35(4):133－144.

［6］Koetter R，M’edard M.An Algebraic Approach to Network Coding［J］.IEEE/ACM Transactionson on Networking，2003，11(5):782－795.

［7］Rozner E，Seshadri J，Mehta Y，et al.Simple Opportunistic Routing Protocol for Wireless Mesh Networks［C］//Proc IEEE Workshop on，Wireless Mesh Networks，Univ of Texas，Austin，Sept 2006:48－54.

［8］Rozner E，Seshadri J，Mebta Y，et al.SOAR:Simple Opportunistic Adaptive Routing Protocol for Wireless Mesh Networks［J］.In IEEE Transactions on Mobile Computing，Dec 2009，8(12):1622－1635.

［9］Jaggi S，Sanders P，Chou P A，et al.Polynomial Time Algorithms for Multicast Network Code Construction［J］.IEEE Transaction on Information Theory，2005，51(6):1973－1982.

［10］Li S Y，Yeung R W，Cai N.Linear Network Coding［J］.IEEE Transactions on Information Theory，2003，49(2):371－381.

［11］Ahlswede R，Cai N，Yeung R W，et al.Network Information Flow［J］.IEEE Transactions on Information Theory，2000，46(4):1204－1216.

［12］熊志強(qiáng)，劉威，程文青，等.基于網(wǎng)絡(luò)編碼的傳感器網(wǎng)絡(luò)信息交換算法研究［J］.傳感技術(shù)學(xué)報(bào)，2008，21(1):141－146.

［13］Chachulski S，Jennings M，Katti S，et al.Trading Structure for Randomness in Wireless Opportunistic Routing［J］.ACM SIGCOMM Computer Communication Review，2007，37(4):169－180.

［14］Lin Y F，Li B C，Liang B.CodeOR:Opportunistic Routing in Wireless Mesh Networks with Segmented Network Coding［C］//Proc of IEEE International Conference on，Network Protocols，Univ of Toronto，Canada，Dec 2008:13－22.

［15］Lin Y F，Li B C，Liang B.Slideor:Online Opportunistic Network Coding in Wireless Mesh Networks［C］//IEEE INFOCOM International Conference on，Computer Communications，Univ of Toronto，Toronto，Canada，2010:171－175.

［16］Koutsonikolas D，Wang C C，Hu Y.CCACK:Efficient Network Coding Based Opportunistic Routing Through Cumulative Coded Acknowledgments［C］//IEEE INFOCOM Conference on，Computer Communications，Purdue Univ，West Lafayette，USA，Mar 2010:1－9.

［17］Couto D De，Aguayo D，Bicket J，et al.A High-Throughput Path Metric for Multi-Hop Wireless Routing［J］.ACM/IEEE MobiCom，2003，11(4):419－434.