一種基于移動(dòng)Sink的容遲網(wǎng)絡(luò)自適應(yīng)機(jī)會(huì)路由算法

徐飚

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都　610000)

一種基于移動(dòng)Sink的容遲網(wǎng)絡(luò)自適應(yīng)機(jī)會(huì)路由算法

徐飚

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610000)

容忍延遲傳感器網(wǎng)絡(luò)；機(jī)會(huì)路由；數(shù)據(jù)收集

0　引言

在容忍延遲移動(dòng)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)[1-2]的研究中，如何提高網(wǎng)絡(luò)數(shù)據(jù)的傳輸成功率和降低并且均衡網(wǎng)絡(luò)能量消耗一直是研究者致力的目標(biāo)和研究熱點(diǎn)。使用移動(dòng)Sink進(jìn)行數(shù)據(jù)收集可以有效提高網(wǎng)絡(luò)性能，這種方法已經(jīng)被廣泛采用，但現(xiàn)存算法有以下不足：不合理的數(shù)據(jù)傳輸方案增大了網(wǎng)絡(luò)時(shí)延[3]，能量消耗過(guò)大，網(wǎng)絡(luò)傳輸延遲較高，且可擴(kuò)展性較差。筆者提出一種高效的基于Sink簡(jiǎn)單軌跡的機(jī)會(huì)路由數(shù)據(jù)傳輸算法（DAOR，Dynamic Adaptive Opportunistic Routing），由數(shù)據(jù)傳輸和隊(duì)列管理兩部分組成，實(shí)驗(yàn)結(jié)果與DT[4]、Flooding[5]和SRAD[6]比較，實(shí)驗(yàn)結(jié)果表明，采用DAOR算法能夠較好地延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間，降低數(shù)據(jù)傳輸時(shí)延以及提高數(shù)據(jù)傳輸成功率。

1　模型與問(wèn)題描述

在半徑為R的圓形監(jiān)測(cè)區(qū)域內(nèi)，隨機(jī)部署N個(gè)不同類(lèi)型的異構(gòu)傳感器，傳感器可以在監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)移動(dòng)。石高濤等[7]等提出一種可負(fù)載平衡的移動(dòng)Sink數(shù)據(jù)收集模式，并證明了當(dāng)緩沖區(qū)為距離圓心R的圓環(huán)時(shí)，網(wǎng)絡(luò)傳輸數(shù)據(jù)消耗能量最小。筆者設(shè)定Sink沿L=R的環(huán)形緩沖區(qū)移動(dòng)并收集數(shù)據(jù)。網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示。網(wǎng)絡(luò)節(jié)點(diǎn)異構(gòu)，節(jié)點(diǎn)運(yùn)動(dòng)符合Random Waypoint（RWP）模型[1]，如圖2。Sink能量不限，發(fā)射功率可控；節(jié)點(diǎn)可感知自己當(dāng)前位置到網(wǎng)絡(luò)原點(diǎn)的距離。

圖1　

圖2　

2　數(shù)據(jù)結(jié)構(gòu)及算法

2.1數(shù)據(jù)包信息結(jié)構(gòu)

對(duì)于所有數(shù)據(jù)包，在其中加入如下結(jié)構(gòu)類(lèi)型信息：

struct info{

int level;

int levelCount;

int position;

}

level表示當(dāng)前副本的復(fù)制層級(jí)。如果當(dāng)前數(shù)據(jù)包由節(jié)點(diǎn)直接產(chǎn)生，則令level=1。levelCount表示該數(shù)據(jù)在level層的副本序數(shù)，每層數(shù)據(jù)副本數(shù)不超過(guò)K。把監(jiān)測(cè)區(qū)域半徑分為I（I〉1）等份，從而把監(jiān)測(cè)區(qū)域分為I個(gè)寬度為的圓環(huán)。每個(gè)圓環(huán)用i（1≤i≤I）表示。當(dāng)節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)時(shí)，節(jié)點(diǎn)位于i環(huán)，令position=i，表示該數(shù)據(jù)包產(chǎn)生位置。

2.2副本復(fù)制算法

當(dāng)兩節(jié)點(diǎn)m，n互相進(jìn)入數(shù)據(jù)傳輸范圍時(shí)，若m攜帶有n沒(méi)有的數(shù)據(jù)包a且n離緩存節(jié)點(diǎn)比m近，則進(jìn)行如下計(jì)算：

（1）若a的levelCount〈K,m將數(shù)據(jù)包a發(fā)送給n。節(jié)點(diǎn)n收到數(shù)據(jù)包后將收到的副本中l(wèi)evelCount加1，其他不變；

（2）若a的levelCount=K且level〈T（T值的計(jì)算見(jiàn)3.3），m將數(shù)據(jù)包a發(fā)送給n。節(jié)點(diǎn)n收到數(shù)據(jù)包后將收到的副本中l(wèi)evel加1，其他不變。

（3）若a的levelCount=K且level=T，則將副本復(fù)制給n后，在m中刪除此副本。

（4）數(shù)據(jù)包生存時(shí)間不斷減少，當(dāng)數(shù)據(jù)包生存時(shí)間為0時(shí)，丟棄數(shù)據(jù)包。

圖3　節(jié)點(diǎn)運(yùn)動(dòng)速度對(duì)傳輸成功率的影響

2.3節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)及算法

在每個(gè)移動(dòng)節(jié)點(diǎn)內(nèi)部設(shè)置一個(gè)數(shù)組A[I]，數(shù)組元素為結(jié)構(gòu)體：

struct meanLevel{ int count;

float meanLevel;

}

A[i](1≤i≤I)表示在第i環(huán)上產(chǎn)生的數(shù)據(jù)包的信息。其中，A[i].count表示第i環(huán)上產(chǎn)生的數(shù)據(jù)包成功傳輸?shù)骄彺婀?jié)點(diǎn)的個(gè)數(shù),A[i].meanLevel表示第i環(huán)上產(chǎn)生的數(shù)據(jù)需要復(fù)制的層數(shù)。

每當(dāng)節(jié)點(diǎn)成功傳輸?shù)趇層產(chǎn)生的數(shù)據(jù)包：

（1）A[i].count=A[i].count+1,當(dāng)A[i].count=c時(shí)，不再增加。c表示轉(zhuǎn)發(fā)層數(shù)計(jì)算的敏感度。

（2）A[i].meanLevel=(A[i].meanLevel*count+info.level)/(count+1)。

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

定義100個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在半徑R=100m的圓形區(qū)域，節(jié)點(diǎn)運(yùn)動(dòng)符合RWP模型。設(shè)網(wǎng)絡(luò)帶寬為10kbit/s,傳輸半徑為2-4m，運(yùn)動(dòng)速率為1-5m/s，節(jié)點(diǎn)初始能量為5-15J。

DT算法中消息副本數(shù)為1，但交付周期過(guò)長(zhǎng)；Flooding算法中產(chǎn)生了大量消息副本；SRAD算法在選擇下一跳時(shí),盡可能選擇與匯聚點(diǎn)進(jìn)行通信的節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，因此傳輸成功率高于DT算法和Flooding算法,但算法并沒(méi)有綜合考慮節(jié)點(diǎn)與匯聚點(diǎn)通信的可能性和能量消耗對(duì)傳輸概率的影響。DAOR算法引入移動(dòng)Sink節(jié)點(diǎn)，在轉(zhuǎn)發(fā)過(guò)程中自適應(yīng)控制消息副本數(shù)量，盡可能利用節(jié)點(diǎn)的移動(dòng)，減少傳輸能耗，因此綜合性能更優(yōu)。

圖4　　節(jié)點(diǎn)運(yùn)動(dòng)速度對(duì)品均時(shí)延的影響

4　結(jié)語(yǔ)

本文通過(guò)在機(jī)會(huì)路由過(guò)程中，根據(jù)產(chǎn)生數(shù)據(jù)位置，自適應(yīng)計(jì)算所需轉(zhuǎn)發(fā)副本數(shù)，在滿(mǎn)足網(wǎng)絡(luò)時(shí)延的前提下，盡可能利用節(jié)點(diǎn)的移動(dòng)攜帶數(shù)據(jù)，減少副本數(shù)量，延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間。該算法復(fù)雜度低，適合移動(dòng)節(jié)點(diǎn)計(jì)算。

[1]劉唐，彭艦，楊進(jìn).異構(gòu)延遲容忍移動(dòng)傳感器網(wǎng)絡(luò)中基于轉(zhuǎn)發(fā)概率的數(shù)據(jù)傳輸［J］.軟件學(xué)報(bào)，2013，24(2):215-229.

[2]楊奎武，郭淵博，鄭康鋒，等.延遲容忍移動(dòng)傳感器 網(wǎng)絡(luò)高效廣播數(shù)據(jù)傳輸機(jī)制［J］.北京郵電大學(xué)學(xué)報(bào)，2013，36(1):1007-5321.

[3]Guerroumi M，Badache N，Moussaoui S.Sink Mobile for Efficient Data Dissemination in Wireless Sensor Networks［J］.Networked Digital Technologies，2012，293(8):635-645.

[4]Wang Yu，Wu Hongyi.Delay/Fault-Tolerant Mobile Sensor Network(DFT-MSN):a New Paradigm for Pervasive Information Gathering ［J］.Mobile Computing，IEEE Transactions on，2007，6(9):1021-1034.

[5]Vahdat A，Becker D.Epidemic Routing for Partially Connected Ad Hoc Networks［R］.Technical Report CS-200006，Duke University，2000.3

[6]朱金奇，劉明，龔海剛，等.延遲容忍移動(dòng)傳感器網(wǎng)絡(luò)中基于選擇復(fù)制的數(shù)據(jù)傳輸［J］.軟件學(xué)報(bào)，2009，20(8):2227-2240.

[7]石高濤，廖明宏.傳感器網(wǎng)絡(luò)中具有負(fù)載平衡的移動(dòng)協(xié)助數(shù)據(jù)收集模式［J］.軟件學(xué)報(bào)，2007，18(9):2235-224.

Delay Tolerant Mobile Sensor Networks;Opportunistic Routing Algorithm;Data Collection

A Dynamic Adaptive Opportunistic Routing Algorithm Based on Mobile Sink in Delay Tolerant Sensor Networks

XU Biao
（College of Computer Science，Sichuan University，Chengdu 610000）

2015-12-20

2015-12-30

提出一種基于Sink簡(jiǎn)單固定軌跡的機(jī)會(huì)路由算法，算法使用改進(jìn)的機(jī)會(huì)路由策略，適用于由移動(dòng)節(jié)點(diǎn)組成的延遲容忍無(wú)線(xiàn)傳感器網(wǎng)絡(luò)。數(shù)據(jù)傳輸采用機(jī)會(huì)路由策略，每次傳輸數(shù)據(jù)包，在包內(nèi)記錄所轉(zhuǎn)發(fā)層數(shù)，通過(guò)自適應(yīng)算法，動(dòng)態(tài)調(diào)整從任意位置將數(shù)據(jù)發(fā)送至Sink路線(xiàn)所需轉(zhuǎn)發(fā)層數(shù)。實(shí)驗(yàn)結(jié)果驗(yàn)證算法的有效性。

徐飚（1988～），男，河南鄭州人，在讀研究生，研究方向?yàn)闊o(wú)線(xiàn)傳感器網(wǎng)絡(luò)、云計(jì)算

Proposes an opportunistic routing algorithm which is based on the simple mobile sink trajectory.It can be applied to delay tolerant mobile sensor network.The data transmission uses opportunistic routing strategy.Every data packet records the level by which it is transmitted. Through dynamic adapting opportunistic routing algorithm the necessary transmission level is counted.Simulations show that this algorithm has a better effectiveness.