DTMSN中基于效用和網(wǎng)絡(luò)編碼的數(shù)據(jù)傳輸

周浩慧

（長沙商貿(mào)旅游職業(yè)技術(shù)學(xué)院 信息系，湖南 長沙 410004）

0 引言

隨著計算機技術(shù)和通信技術(shù)的快速發(fā)展，通信網(wǎng)絡(luò)與人們的生活聯(lián)系越來越緊密。為了滿足人們對網(wǎng)絡(luò)應(yīng)用多元化的需求，近年來出現(xiàn)了很多滿足特殊應(yīng)用的網(wǎng)絡(luò)，無線傳感器網(wǎng)絡(luò)就是其中的一種。無線傳感器網(wǎng)絡(luò)是能在任何時間、任何地點、任何環(huán)境下快速組網(wǎng)并完成一定感知任務(wù)的無線自組織網(wǎng)絡(luò)，如車載傳感器網(wǎng)絡(luò)、氣象監(jiān)測傳感器網(wǎng)絡(luò)、移動水下設(shè)備傳感器網(wǎng)絡(luò)以及森林環(huán)境監(jiān)測傳感器網(wǎng)絡(luò)。

然而在一些特殊的環(huán)境下應(yīng)用無線傳感器網(wǎng)絡(luò)時，由于某些原因，網(wǎng)絡(luò)大部分時間是不連通的，傳統(tǒng)的無線傳感器網(wǎng)絡(luò)要求通信的2個節(jié)點之間至少存在1條完整的路徑，這種特殊的無線傳感器網(wǎng)絡(luò)是通過節(jié)點的移動帶來的相遇機會實現(xiàn)通信，稱之為延遲容忍移動無線傳感器網(wǎng)絡(luò)（Delay Tolerant Mobile Sensor Networks，DTMSN）[1]。隨著DTMSN在實際的應(yīng)用增多，越來越多的研究人員投入到DTMSN的研究中，而且在DTMSN數(shù)據(jù)傳輸?shù)难芯可先〉昧艘恍┏晒匀徊荒軡M足在特殊環(huán)境中應(yīng)用的需求，筆者在DTMSN中引入網(wǎng)絡(luò)編碼[2]，主要研究在DTMSN的數(shù)據(jù)傳輸中使用網(wǎng)絡(luò)編碼來優(yōu)化DTMSN的傳輸性能。

1 DTMSN和網(wǎng)絡(luò)編碼

1.1 DTMSN

DTMSN由2種節(jié)點組成：傳感器節(jié)點和匯聚節(jié)點（Sink），傳感器節(jié)點放置在隨機運動體上并形成一個間歇性連通利用節(jié)點移動實現(xiàn)通信的無線傳感器網(wǎng)絡(luò)，匯聚節(jié)點是放置在某固定位置或運動體上用來收集數(shù)據(jù)的超級節(jié)點，是所有源傳感器節(jié)點數(shù)據(jù)回傳的終點。一方面，DTMSN具有傳統(tǒng)無線傳感器網(wǎng)絡(luò)[3]的很多特性，如傳感器節(jié)點的傳輸距離短、計算能力弱、存儲空間和能源非常有限等。另一方面，與傳統(tǒng)無線傳感器網(wǎng)絡(luò)相比，DTMSN又具有如下特性：1）隨機移動的節(jié)點。由于傳感器節(jié)點或Sink節(jié)點是放在隨機運動體上，節(jié)點的隨機運動導(dǎo)致網(wǎng)絡(luò)的拓撲是動態(tài)變化的。2）連通間歇性。DTMSN的連通性比較差，網(wǎng)絡(luò)中的一些節(jié)點之間的連通是偶爾的。3）延遲容忍。DTMSN中數(shù)據(jù)傳輸?shù)难舆t很高，在使用時要能夠容忍延遲。4）較差的可靠性。DTMSN中數(shù)據(jù)的傳輸成功率較低，數(shù)據(jù)交付的可靠性比較差。

目前DTMSN還沒有一個比較統(tǒng)一的定義，筆者參照現(xiàn)有一些文獻分析DTMSN的特點，給出一個描述性定義：DTMSN是一種不需要傳感器節(jié)點和匯聚節(jié)點之間存在完整鏈路，利用節(jié)點移動帶來的相遇機會，實現(xiàn)廣泛數(shù)據(jù)收集的新型無線傳感器網(wǎng)絡(luò)。DTMSN的路由模式是“存儲—攜帶—轉(zhuǎn)發(fā)”。圖1是DTMSN示意圖，t1時刻源傳感器節(jié)點1希望將數(shù)據(jù)傳輸給固定位置的Sink節(jié)點，但節(jié)點1和Sink節(jié)點間沒有一條完整的通信鏈路，因此，1將數(shù)據(jù)發(fā)送給鄰居節(jié)點2，2再將數(shù)據(jù)轉(zhuǎn)發(fā)給3，由于3沒有合適的下一跳可轉(zhuǎn)發(fā)，它將數(shù)據(jù)在本地存儲并等待傳輸機會，過一段時間到達t2時刻，通過運動節(jié)點3和節(jié)點6相遇，3將存儲的數(shù)據(jù)轉(zhuǎn)發(fā)給6，t3時刻，6將數(shù)據(jù)傳輸給Sink節(jié)點，完成數(shù)據(jù)傳輸。

1.2 網(wǎng)絡(luò)編碼

網(wǎng)絡(luò)編碼理論[4]作為21世紀(jì)初信息論領(lǐng)域中一大重要突破，是由香港中文大學(xué)的Ahlswede等人提出，該理論改變傳統(tǒng)中間節(jié)點對輸入的信息流只進行轉(zhuǎn)發(fā)的模式，通過允許中間節(jié)點對輸入信息流在轉(zhuǎn)發(fā)前進行編碼，并保證接收節(jié)點能正確地恢復(fù)源節(jié)點所發(fā)送的信息，從而達到網(wǎng)絡(luò)通信的最大容量，最大限度地利用網(wǎng)絡(luò)現(xiàn)有的資源。網(wǎng)絡(luò)編碼最初是為有線網(wǎng)絡(luò)而提出的，但經(jīng)過大量研究卻發(fā)現(xiàn)無線網(wǎng)絡(luò)中鏈路的不可靠性和物理廣播特性非常適合網(wǎng)絡(luò)編碼。因此，網(wǎng)絡(luò)編碼被應(yīng)用去解決各種無線網(wǎng)絡(luò)問題，并且取得了一定的成果，DTMSN作為無線網(wǎng)絡(luò)的一種同樣適合網(wǎng)絡(luò)編碼。

圖2是簡單的網(wǎng)絡(luò)編碼示意圖，假設(shè)每條鏈路的容量為每單位時間1 bit，源節(jié)點S向目標(biāo)節(jié)點D1和D2同時發(fā)送2 bit信息a和b。圖2a采用傳統(tǒng)的組播技術(shù)，節(jié)點S把信息a和b分別發(fā)送給1和2，節(jié)點1和2將收到的數(shù)據(jù)再轉(zhuǎn)發(fā)給其他節(jié)點。節(jié)點1直接得到a，節(jié)點2直接得到b。當(dāng)a和b到達節(jié)點3要進行轉(zhuǎn)發(fā)時，由于節(jié)點3和4之間只有1條鏈路且鏈路的容量為1 bit，因此信息a或b必須在節(jié)點3處排隊等候1個單位時間。如此一來，這2個目標(biāo)節(jié)點在單位時間內(nèi)接收到的信息為1.5 bit。圖2b使用網(wǎng)絡(luò)編碼，中間節(jié)點3將收到的信息a和b進行編碼，得到a⊕b，然后將編碼后的信息轉(zhuǎn)發(fā)出去。目標(biāo)節(jié)點D1接收到信息a和編碼后的信息a⊕b，通過運算解碼出b。同樣，在目標(biāo)節(jié)點D2上也通過運算解碼出a。這樣這2個目標(biāo)節(jié)點在單位時間內(nèi)接收到的信息接近2 bit。

圖2 2種信息處理方式示意圖

網(wǎng)絡(luò)編碼作為信息論和網(wǎng)絡(luò)技術(shù)的融合，在提高網(wǎng)絡(luò)吞吐量、節(jié)約能耗、增強可靠性和安全性等方面表現(xiàn)突出，但同時也增加了節(jié)點的計算開銷。由于近幾十年計算機技術(shù)的快速發(fā)展，現(xiàn)在網(wǎng)絡(luò)傳輸?shù)钠款i不是計算量而是網(wǎng)絡(luò)帶寬和服務(wù)質(zhì)量。網(wǎng)絡(luò)編碼的核心就是利用計算機強大的計算能力換取在網(wǎng)絡(luò)帶寬方面的提高以及安全性和可靠性方面的增強。

2 基于效用和網(wǎng)絡(luò)編碼的數(shù)據(jù)傳輸

在DTMSN中加入其他技術(shù)和設(shè)計出適合的數(shù)據(jù)傳輸策略來提高DTMSN的性能，已經(jīng)成為DTMSN研究中的重要內(nèi)容。基于網(wǎng)絡(luò)編碼的數(shù)據(jù)傳輸是將待傳輸?shù)臄?shù)據(jù)通過某種編碼方法編碼成相互冗余的數(shù)據(jù)消息，目的節(jié)點只要收到一定數(shù)量編碼后的數(shù)據(jù)消息就可以通過運算恢復(fù)出原數(shù)據(jù)。基于復(fù)制的數(shù)據(jù)傳輸是在網(wǎng)絡(luò)中注入大量冗余信息，提高了數(shù)據(jù)傳輸?shù)某晒β剩珔s加大了整個網(wǎng)絡(luò)的負擔(dān)。基于效用的數(shù)據(jù)傳輸能在一定程度上避免節(jié)點之間數(shù)據(jù)轉(zhuǎn)發(fā)的盲目性，減少數(shù)據(jù)傳輸次數(shù)，提高數(shù)據(jù)傳輸成功率，可是卻加重了部分節(jié)點的負擔(dān)，造成了某些鏈路的嚴(yán)重擁塞。而基于效用和網(wǎng)絡(luò)編碼的數(shù)據(jù)傳輸能在提高數(shù)據(jù)傳輸成功率的同時很好地均衡網(wǎng)絡(luò)開銷，有效減少數(shù)據(jù)傳輸次數(shù)和傳輸延遲，最終實現(xiàn)DTMSN性能的最大化。

2.1 SF數(shù)據(jù)傳輸策略

Spray and Focus（SF）[5]是一種基于效用的數(shù)據(jù)傳輸策略，該策略改進了基于復(fù)制的Spray and Wait（SW）[6]數(shù)據(jù)傳輸策略的Wait階段。SF分為Spray和Focus 2個階段，在Spray階段，源節(jié)點生成1個數(shù)據(jù)后產(chǎn)生該數(shù)據(jù)的L（L＞1）份副本，使用某種分發(fā)策略將這L份副本分發(fā)給其他沒有緩存該數(shù)據(jù)的中繼節(jié)點，當(dāng)分發(fā)任務(wù)完成后，節(jié)點進入Focus階段，在Focus階段，每個節(jié)點都與其相遇的節(jié)點維持1個效用值，這樣網(wǎng)絡(luò)中的數(shù)據(jù)不斷從效用值較低的節(jié)點經(jīng)“存儲—攜帶—轉(zhuǎn)發(fā)”傳送到效用值高的節(jié)點，直到與目標(biāo)節(jié)點相遇完成數(shù)據(jù)的傳輸。假如節(jié)點的效用值在網(wǎng)絡(luò)中分布適當(dāng)，SF可在很大程度上提高網(wǎng)絡(luò)的傳輸性能。

2.2 SF-NC數(shù)據(jù)傳輸策略

1）定義1[7]

平均連接頻率（ACF）fi,j是指節(jié)點i和節(jié)點j在單位時間內(nèi)聯(lián)系的次數(shù)，公式為

式中：T指預(yù)先定義的固定時長，Ni,j是指在T時間內(nèi)節(jié)點i和j聯(lián)系的次數(shù)。

2）定義2[8]

Ci是指節(jié)點i在一段時間內(nèi)與網(wǎng)路內(nèi)其他節(jié)點的連接次數(shù)不小于1的節(jié)點數(shù)，公式為

式中：N是網(wǎng)絡(luò)中的節(jié)點數(shù)，T指預(yù)先定義的固定時長，如果在T時間段內(nèi)Ni,j不小于1，那么ET(i,j)=1，否則ET(i,j)=0。

2.2.1 策略描述

在DTMSN中，假設(shè)每個節(jié)點都有1個唯一的ID且每個節(jié)點都與其相遇的節(jié)點維持1個C值并與Sink節(jié)點維持1個ACF值，每T時間內(nèi)更新節(jié)點的ACF值和C值。SF-NC中的Spray階段采用C-Binary分發(fā)策略，該分發(fā)策略改進了SF中Spray階段副本擴散的局部性弊端，并且為網(wǎng)絡(luò)編碼提供了好的編碼環(huán)境，源傳感器節(jié)點生成1個數(shù)據(jù)后產(chǎn)生該數(shù)據(jù)的L（L＞1）份副本，使用交換機制分發(fā)給未緩存該數(shù)據(jù)的中繼節(jié)點，在分發(fā)過程中，當(dāng)遇到未緩存該數(shù)據(jù)的節(jié)點時，就將數(shù)據(jù)的1份副本給它，然后這2個節(jié)點按一定比例來分配當(dāng)前剩余副本的分發(fā)任務(wù)，這個比例就是這2個節(jié)點C的比值，C-Binary分發(fā)策略能很好地將同一個數(shù)據(jù)的副本在網(wǎng)絡(luò)中擴散開。當(dāng)分發(fā)任務(wù)完成后，節(jié)點進入Focus階段，在Focus階段使用網(wǎng)絡(luò)編碼，采用以下2個機制觸發(fā)編碼器：1）緩存隊列滿時。2）遇到比自己ACF值高的節(jié)點要轉(zhuǎn)發(fā)數(shù)據(jù)時。中間節(jié)點將編碼后的數(shù)據(jù)消息廣播，只有ACF值比該節(jié)點ACF大的節(jié)點才接收此數(shù)據(jù)消息，并放入緩存隊列中等待，Sink節(jié)點的ACF值可看成是無窮大，T可根據(jù)網(wǎng)絡(luò)的實際情況來設(shè)定。

2.2.2 策略中數(shù)據(jù)消息在節(jié)點的處理過程

隨機線性網(wǎng)絡(luò)編碼[9-11]是指每個消息都對應(yīng)1個在有限域中隨機選取的編碼系數(shù)，這些消息和其對應(yīng)的編碼系數(shù)通過加和乘運算組成線性組合的一種編碼方法。策略使用離散時間模型[12]，把在源傳感器節(jié)點的數(shù)據(jù)產(chǎn)生分成離散的時間段，這里稱時間段為“代”，每“代”產(chǎn)生的數(shù)據(jù)有1個相同的標(biāo)識，只有擁有相同標(biāo)識的數(shù)據(jù)才能進行編碼。每個節(jié)點都將收到的相同標(biāo)識的信息向量和對應(yīng)的編碼向量放在1個解碼矩陣中存儲。Sink節(jié)點按“代”將收到的數(shù)據(jù)消息分別放入解碼矩陣中，當(dāng)單個信息向量包含的源數(shù)據(jù)個數(shù)等于解碼矩陣的秩時，能解碼出對應(yīng)的源數(shù)據(jù)。例如，中間節(jié)點A，B1，B2，…，Bn，目的節(jié)點為Sink節(jié)點，則fA表示節(jié)點A的ACF值，GAr表示節(jié)點A的r代解碼矩陣，fBi表示節(jié)點Bi的ACF值表示節(jié)點Bi的r代解碼矩陣。(gAr(t),yAr(t))表示A節(jié)點在t時刻發(fā)出的編碼向量和信息向量的元組，GAr(t)表示節(jié)點A在t時刻r代的解碼矩陣，Rr(t)是1個在有限域中隨機取的不為0的系數(shù)向量。假設(shè)則算法為：

1）在t時刻，假如節(jié)點A滿足以上2種觸發(fā)機制中的任何一種就觸發(fā)編碼器進行編碼，得到

假如是第1種機制觸發(fā)，編碼后再存儲，假如是第2種機制觸發(fā)，就轉(zhuǎn)發(fā)元組(gAr(t),yAr(t))。

2）假如不能觸發(fā)編碼器，則再等待t1時間，即t+=wait(t1)，返回 1）。Bi節(jié)點收到(gAr(t),yAr(t))后將其插到自己的解碼矩陣GBir中，如果插入后增加了解碼矩陣的秩就存儲，否則忽略。為快速解碼源數(shù)據(jù)，一般使用高斯消元法讓解碼矩陣保持簡化形式。

3 仿真和性能分析

使用NS2進行仿真，仿真環(huán)境為：將60個傳感器節(jié)點放在60個運動體上，然后在1個3 000 m×3 000 m的區(qū)域內(nèi)隨機部署，1個Sink節(jié)點固定在1 500 m×1 500 m處，每個節(jié)點的通信范圍是80 m，在其中選5個節(jié)點作為源傳感器節(jié)點向Sink節(jié)點發(fā)送信息，源傳感器節(jié)點和Sink節(jié)點之間幾乎不存在完整的鏈路，傳感器節(jié)點的移動模型為Random-Waypoint，設(shè)定SF-NC算法中隨機線性網(wǎng)絡(luò)編碼的編碼向量是基于有限域GF（28）。

筆者模擬實現(xiàn)了SF-NC，F(xiàn)AD和泛洪算法，分別將它們在傳感器節(jié)點不同移動速度和不同存儲隊列長度下，對數(shù)據(jù)的傳輸成功率和平均傳輸時間進行比較。仿真結(jié)果如圖3和圖4所示。

在DTMSN實際環(huán)境中，為了提高數(shù)據(jù)傳輸?shù)某晒β剩坏貌幌蚓W(wǎng)絡(luò)中注入大量冗余信息，因此網(wǎng)絡(luò)相對比較繁忙，網(wǎng)絡(luò)越繁忙傳感器節(jié)點存儲受限問題就越突出，但此卻非常適合進行網(wǎng)絡(luò)編碼，使用網(wǎng)絡(luò)編碼經(jīng)1次編碼就可以完成多次發(fā)送任務(wù)，而基于效用值的傳輸能很好地控制副本的數(shù)量。這樣就很大程度上緩解了節(jié)點存儲受限問題，而且大大提高了傳輸效率，減輕了網(wǎng)絡(luò)的負荷，減少了節(jié)點的能量消耗，縮短了數(shù)據(jù)傳輸?shù)臅r延。

可以看到SF-NC數(shù)據(jù)傳輸策略能以較低的數(shù)據(jù)傳輸延遲獲得較高的數(shù)據(jù)傳輸成功率。由于該策略能有效利用局部連通機會，通過網(wǎng)絡(luò)編碼使節(jié)點間以最有效的方式傳輸數(shù)據(jù)，減輕網(wǎng)絡(luò)的擁塞，節(jié)省傳感器節(jié)點的存儲空間，讓節(jié)點存儲的數(shù)據(jù)能在有限的相遇時間內(nèi)以最快的方式轉(zhuǎn)發(fā)出去。這樣既減少了傳輸次數(shù)，又充分利用了節(jié)點間難得的相遇機會，當(dāng)節(jié)點的ACF值在網(wǎng)絡(luò)中分布適當(dāng)并且L的值適合時，SF-NC能極大地提高DTMSN的傳輸性能。

4 小結(jié)

筆者把網(wǎng)絡(luò)編碼引入到DTMSN中，結(jié)合基于效用的SF數(shù)據(jù)傳輸策略，設(shè)計出了SF-NC數(shù)據(jù)傳輸策略，相比DTMSN中現(xiàn)有的幾種數(shù)據(jù)傳輸策略，在整體性能上有很大的提升。網(wǎng)絡(luò)編碼作為通信領(lǐng)域的重大突破，隨著對網(wǎng)絡(luò)編碼研究的不斷深入，將給無線網(wǎng)絡(luò)的發(fā)展帶來革命性的變化，DTMSN作為一種新型的無線自組織網(wǎng)絡(luò)，把它與網(wǎng)絡(luò)編碼結(jié)合對DTMSN的發(fā)展將產(chǎn)生具有深遠意義的影響。下一步將更加深入地研究網(wǎng)絡(luò)編碼在DTMSN中的應(yīng)用。

[1]WANG Yu，LIN Feng，WU Hongyi.Efficient data transmission in delay fault tolerant mobile sensor networks（DFT-MSN）[EB/OL].[2010-12-20].http：//www.ieee-icnp.org/2005/Posters/Wang.pdf.

[2]羅峰.基于網(wǎng)絡(luò)編碼的P2P網(wǎng)絡(luò)系統(tǒng)研究[J].電視技術(shù)，2007，31（2）：60-63.

[3]孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005：4-57.

[4]AHLSWEDE R，CAI N，LI S Y R，et a1.Network information flow[J].IEEE Trans.Information Theory，2000，46（4）：1204-1216.

[5]SPYROPOULOS T，PSOUNIS K，RAGHAVENDRA C S.Spray and Focus：efficient mobility-assisted routing for heterogeneous and correlated mobility[EB/OL].[2010-12-20].http：//citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.126.5674＆rep=rep1＆type=pdf.

[6]SPYROPOULOS T，PSOUNIS K，RAGHAVENDRA C S.Spray and Wait：an efficient routing scheme for intermittently connected mobile networks[EB/OL].[2010-12-20].http：//conferences.sigcomm.org/sigcomm/2005/paper-SpyPso.pdf.

[7]WANG Yong，JAIN S，MARTONOSI M，et al.Erasure-coding based routing for opportunistic networks[EB/OL].[2010-12-20].http：//citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.364＆rep=rep1＆type=pdf.

[8]王建新，朱敬，劉耀.基于副本限制和社會性的延遲容忍網(wǎng)絡(luò)路由算法[J].華南理工大學(xué)學(xué)報：自然科學(xué)版，2009（5）：84-89.

[9]HO T，MEDARD M，KOETTER R，et al.A random linear network coding approach to multicast[J].IEEE Trans.Information Theory，2006，52（10）：4413-4430.

[10]LI S Y R，YEUNG R W，CAI Ning.Linear network coding[J].IEEE Trans.Information Theory，2003，49（2）：371-381.

[11]WANG D，ZHANG Q，LIU J.Partial network coding：concept，performance，and application for continuous data collection in sensor networks[EB/OL].[2010-12-20].http：//www4.comp.polyu.edu.hk/～csdwang/Publication/TOSN-PNC.pdf.

[12]WIDMER J，BOUDEC J L.Network coding for efficient communication in extreme networks[EB/OL].[2010-12-20].http：//citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.5368＆rep=rep1＆type=pdf.