田賢忠,劉 強(qiáng),胡同森
(浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023)
傳統(tǒng)無(wú)線自組織網(wǎng)絡(luò)和傳感器網(wǎng)絡(luò)的路由協(xié)議都采用確定性路由[1-3]方式,即:在端到端的數(shù)據(jù)傳輸過(guò)程中,首先建立一條端到端的節(jié)點(diǎn)序列,然后在每次分組轉(zhuǎn)發(fā)時(shí),首先確定一個(gè)下一跳節(jié)點(diǎn),再執(zhí)行鏈路層轉(zhuǎn)發(fā)。如果傳輸過(guò)程中發(fā)生分組丟失或差錯(cuò),則啟動(dòng)鏈路層重傳。在鏈路質(zhì)量和穩(wěn)定性較差的環(huán)境下,頻繁的鏈路層數(shù)據(jù)重傳將消耗大量的帶寬資源。因此,盡管確定性路由方式邏輯簡(jiǎn)單,但未能充分考慮無(wú)線信道的廣播特性、時(shí)變特性和干擾不規(guī)則性等特點(diǎn)。無(wú)線信道的廣播特性使得一次分組轉(zhuǎn)發(fā)可能被多個(gè)節(jié)點(diǎn)收到,且接收概率各不相同;無(wú)線鏈路的時(shí)變特性導(dǎo)致網(wǎng)絡(luò)中鏈路的狀態(tài)隨時(shí)間而改變。路由協(xié)議設(shè)計(jì)過(guò)程中如果缺乏對(duì)信道廣播和丟失特性的充分考慮,必將導(dǎo)致大量網(wǎng)絡(luò)資源無(wú)謂浪費(fèi),這將嚴(yán)重影響網(wǎng)絡(luò)的吞吐量及其它性能。
針對(duì)無(wú)線信道的廣播、時(shí)變、丟失特性和確定性路由策略的不足,麻省理工學(xué)院(MIT)的Biswas等人于2004年率先提出了機(jī)會(huì)路由[4-5]的概念。機(jī)會(huì)路由通過(guò)多個(gè)潛在中繼節(jié)點(diǎn)競(jìng)爭(zhēng)、自主智能進(jìn)行下一跳節(jié)點(diǎn)選擇。它充分利用了信道廣播特性,提高了網(wǎng)絡(luò)的吞吐量和傳輸可靠性。研究機(jī)會(huì)路由算法[6-8]來(lái)提升無(wú)線多跳網(wǎng)絡(luò)的性能,已成為當(dāng)前無(wú)線自組織網(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無(wú)關(guān)的協(xié)議,它通過(guò)引入網(wǎng)絡(luò)編碼解決了數(shù)據(jù)傳輸過(guò)程中節(jié)點(diǎn)協(xié)作難的問(wèn)題,即:轉(zhuǎn)發(fā)節(jié)點(diǎn)可以不管其他節(jié)點(diǎn)發(fā)送的是什么數(shù)據(jù),而只需要將自己緩存下來(lái)的數(shù)據(jù)進(jìn)行編碼后轉(zhuǎn)發(fā)出去即可,目的節(jié)點(diǎn)收到一定數(shù)量的編碼包后解出相應(yīng)的原數(shù)據(jù)包。同時(shí)它充分利用了網(wǎng)絡(luò)的空間關(guān)系,通過(guò)多個(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)信息后才開(kāi)始發(fā)送下一段數(shù)據(jù),這樣就影響了網(wǎng)絡(luò)的吞吐量。為此,Lin Y[14-15]等人給出了兩種不同的解決方案:文獻(xiàn)[14]同樣是采用分段的形式傳輸,但能夠同時(shí)傳輸多個(gè)段,效率有一定的提高,但是存在ACK數(shù)量較多的問(wèn)題,它在一定程度上占用了網(wǎng)絡(luò)帶寬資源;文獻(xiàn)[15]則從另一個(gè)方面入手來(lái)解決MORE的問(wèn)題,它摒棄了段的概念,將數(shù)據(jù)看成一個(gè)很長(zhǎng)的流,采用“滑動(dòng)窗口”的形式進(jìn)行傳輸,也在一定程度上解決了MORE的問(wèn)題。文獻(xiàn)[16]則從另一個(gè)角度發(fā)揮機(jī)會(huì)路由與網(wǎng)絡(luò)編碼的優(yōu)勢(shì),它用個(gè)一種新的確認(rèn)機(jī)制來(lái)壓縮傳統(tǒng)ACK確認(rèn)機(jī)制帶來(lái)的開(kāi)銷(xiāo),在一定程度上改善了網(wǎng)絡(luò)的性能。
從上面的分析可以看出,提高網(wǎng)絡(luò)的吞吐量需從兩個(gè)方面著手:(1)發(fā)送ACK確認(rèn)信息要及時(shí);(2)發(fā)的ACK確認(rèn)信息要少。為此,本文提出一種最大限度的壓縮ACK的機(jī)制,我們稱(chēng)之為MinACK算法。它較為及時(shí)地發(fā)送ACK,從而允許同時(shí)在網(wǎng)絡(luò)中傳輸多個(gè)數(shù)據(jù)段;同時(shí)每發(fā)送一段數(shù)據(jù)只需回一個(gè)ACK,減少了ACK的發(fā)送。另外,它還與MAC無(wú)關(guān),省去了許多節(jié)點(diǎn)之間協(xié)作的開(kāi)銷(xiāo),從而進(jìn)一步提高網(wǎng)絡(luò)的吞吐量。我們?cè)诜抡鎸?shí)驗(yàn)中也充分證明了MinACK的優(yōu)勢(shì)所在。
如圖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ā)送過(guò)來(lái)的編碼包后,與各自之前已收到的同一數(shù)據(jù)段的編碼包重新編碼后再發(fā)送。目的節(jié)點(diǎn)D收到K個(gè)線性無(wú)關(guān)的編碼包后解出原始數(shù)據(jù)包,并發(fā)送一個(gè)確認(rèn)信息ACK給源節(jié)點(diǎn)S。源節(jié)點(diǎn)S在收到ACK后發(fā)送下一段數(shù)據(jù)包。這樣有一個(gè)問(wèn)題,目的節(jié)點(diǎn)D在能解碼時(shí),源節(jié)點(diǎn)S不能馬上發(fā)送下一段的數(shù)據(jù)包,必須等到收到ACK后才開(kāi)始發(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è))的線性無(wú)關(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中含有足夠多的線性無(wú)關(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è)線性無(wú)關(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競(jìng)爭(zhēng)獲得信道后向下一跳節(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也收到了,也就是說(shuō)節(jié)點(diǎn)w不但收到上一跳節(jié)點(diǎn)u的編碼包,也收到同層節(jié)點(diǎn)v的編碼包。不管哪種情況,節(jié)點(diǎn)w對(duì)收到的編碼包也判斷是否與之前收到的同一段的編碼包線性相關(guān),如果線性無(wú)關(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。
上面的算法中,有幾個(gè)問(wèn)題必須明確:(1)如何確定下一跳節(jié)點(diǎn);(2)編碼解碼策略;(3)節(jié)點(diǎn)轉(zhuǎn)發(fā)編碼包數(shù)目;(4)ACK確認(rè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)通過(guò)周期性的互相探測(cè)來(lái)獲得每條鏈路的成功傳輸率,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)。
編碼包在轉(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)的編碼向量,通過(guò)高斯消元即可解碼出原始包。
當(dāng)一個(gè)節(jié)點(diǎn)收到一個(gè)編碼包后,會(huì)觸發(fā)其重新編碼后向下一跳節(jié)點(diǎn)發(fā)送編碼包。那么應(yīng)該發(fā)送多少個(gè)編碼包?按傳統(tǒng)方法每收到一個(gè)發(fā)送一個(gè)會(huì)帶來(lái)兩個(gè)問(wèn)題:①由于丟包,只發(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清零。
當(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后刪除緩存中這一段的編碼包,開(kāi)始發(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包格式
MinACK能在網(wǎng)絡(luò)中同時(shí)傳輸多個(gè)數(shù)據(jù)段,從而提高網(wǎng)絡(luò)的吞吐量。這里分析網(wǎng)絡(luò)中能同時(shí)傳輸?shù)臄?shù)據(jù)段數(shù)以及網(wǎng)絡(luò)的吞吐量。
從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ù)量來(lái)判斷網(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í)際傳輸中很容易記錄下來(lái),但理論計(jì)算比較難。我們用另一種思路來(lái)計(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(下面稱(chēng)“路徑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(下面稱(chēng)“路徑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ù)為L(zhǎng)v,根據(jù)式(2),可以求出所有節(jié)點(diǎn)的發(fā)送次數(shù),即網(wǎng)絡(luò)中同時(shí)傳輸?shù)臄?shù)據(jù)段數(shù)為:
網(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í)間為T(mén)total,假設(shè)每個(gè)編碼包的大小是M,則吞吐量
本文使用Matlab語(yǔ)言對(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我們是通過(guò)傳輸50個(gè)包,改變節(jié)點(diǎn)間的傳輸成功率(從0.1到0.9變化)統(tǒng)計(jì)三者的傳輸次數(shù)得到的。從仿真結(jié)果看節(jié)點(diǎn)間的傳輸成功率越低,MinACK和MORE的優(yōu)勢(shì)較之ExOR就越明顯;圖5我們是通過(guò)改變傳輸包的個(gè)數(shù),而節(jié)點(diǎn)間的傳輸概率不變得到的。總體上都是隨著數(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的吞吐量性能好,接下來(lái)的吞吐量仿真也充分證明了這一點(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是我們通過(guò)傳輸500個(gè)數(shù)據(jù)包,讓K(每段中數(shù)據(jù)包的個(gè)數(shù))從10到100之間變化得到的,從仿真結(jié)果看隨著K的增大,三者的吞吐量相差越來(lái)越??;圖8中K固定為50,通過(guò)改變傳輸數(shù)據(jù)包的個(gè)數(shù)得到的,從仿真結(jié)果可以看出,三者的吞吐量隨傳輸包的個(gè)數(shù)變化不大。在K較小的新情況下,MORE的吞吐量大概是ExOR的1.2倍左右,MinACK的吞吐量大概是MORE的1.2倍左右,是ExOR的的1.45倍左右,可見(jiàn)吞吐量性能有了不少的提高。
本文提出了一種基于網(wǎng)絡(luò)編碼的機(jī)會(huì)路由算法-MinACK,它結(jié)合了網(wǎng)絡(luò)編碼與機(jī)會(huì)路由的優(yōu)點(diǎn),通過(guò)在網(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ú)線網(wǎng)絡(luò)的傳輸機(jī)制是作者下一步要研究的內(nèi)容。
[1]程大偉,趙海,張希元,等.基于EWMA的無(wú)線傳感器網(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)國(guó),李國(guó)徽.一種面向目標(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.