一種基于移動Sink的容遲網絡自適應機會路由算法

徐飚

（四川大學計算機學院，成都　610000)

一種基于移動Sink的容遲網絡自適應機會路由算法

徐飚

（四川大學計算機學院，成都610000)

容忍延遲傳感器網絡；機會路由；數據收集

0　引言

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

1　模型與問題描述

在半徑為R的圓形監測區域內，隨機部署N個不同類型的異構傳感器，傳感器可以在監測區域內隨機移動。石高濤等[7]等提出一種可負載平衡的移動Sink數據收集模式，并證明了當緩沖區為距離圓心R的圓環時，網絡傳輸數據消耗能量最小。筆者設定Sink沿L=R的環形緩沖區移動并收集數據。網絡結構如圖1所示。網絡節點異構，節點運動符合Random Waypoint（RWP）模型[1]，如圖2。Sink能量不限，發射功率可控；節點可感知自己當前位置到網絡原點的距離。

圖1　

圖2　

2　數據結構及算法

2.1數據包信息結構

對于所有數據包，在其中加入如下結構類型信息：

struct info{

int level;

int levelCount;

int position;

}

level表示當前副本的復制層級。如果當前數據包由節點直接產生，則令level=1。levelCount表示該數據在level層的副本序數，每層數據副本數不超過K。把監測區域半徑分為I（I〉1）等份，從而把監測區域分為I個寬度為的圓環。每個圓環用i（1≤i≤I）表示。當節點產生數據時，節點位于i環，令position=i，表示該數據包產生位置。

2.2副本復制算法

當兩節點m，n互相進入數據傳輸范圍時，若m攜帶有n沒有的數據包a且n離緩存節點比m近，則進行如下計算：

（1）若a的levelCount〈K,m將數據包a發送給n。節點n收到數據包后將收到的副本中levelCount加1，其他不變；

（2）若a的levelCount=K且level〈T（T值的計算見3.3），m將數據包a發送給n。節點n收到數據包后將收到的副本中level加1，其他不變。

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

（4）數據包生存時間不斷減少，當數據包生存時間為0時，丟棄數據包。

圖3　節點運動速度對傳輸成功率的影響

2.3節點數據結構及算法

在每個移動節點內部設置一個數組A[I]，數組元素為結構體：

struct meanLevel{ int count;

float meanLevel;

}

A[i](1≤i≤I)表示在第i環上產生的數據包的信息。其中，A[i].count表示第i環上產生的數據包成功傳輸到緩存節點的個數,A[i].meanLevel表示第i環上產生的數據需要復制的層數。

每當節點成功傳輸第i層產生的數據包：

（1）A[i].count=A[i].count+1,當A[i].count=c時，不再增加。c表示轉發層數計算的敏感度。

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

3　仿真實驗

定義100個傳感器節點隨機分布在半徑R=100m的圓形區域，節點運動符合RWP模型。設網絡帶寬為10kbit/s,傳輸半徑為2-4m，運動速率為1-5m/s，節點初始能量為5-15J。

DT算法中消息副本數為1，但交付周期過長；Flooding算法中產生了大量消息副本；SRAD算法在選擇下一跳時,盡可能選擇與匯聚點進行通信的節點轉發消息，因此傳輸成功率高于DT算法和Flooding算法,但算法并沒有綜合考慮節點與匯聚點通信的可能性和能量消耗對傳輸概率的影響。DAOR算法引入移動Sink節點，在轉發過程中自適應控制消息副本數量，盡可能利用節點的移動，減少傳輸能耗，因此綜合性能更優。

圖4　　節點運動速度對品均時延的影響

4　結語

本文通過在機會路由過程中，根據產生數據位置，自適應計算所需轉發副本數，在滿足網絡時延的前提下，盡可能利用節點的移動攜帶數據，減少副本數量，延長網絡生存時間。該算法復雜度低，適合移動節點計算。

[1]劉唐，彭艦，楊進.異構延遲容忍移動傳感器網絡中基于轉發概率的數據傳輸［J］.軟件學報，2013，24(2):215-229.

[2]楊奎武，郭淵博，鄭康鋒，等.延遲容忍移動傳感器 網絡高效廣播數據傳輸機制［J］.北京郵電大學學報，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]朱金奇，劉明，龔海剛，等.延遲容忍移動傳感器網絡中基于選擇復制的數據傳輸［J］.軟件學報，2009，20(8):2227-2240.

[7]石高濤，廖明宏.傳感器網絡中具有負載平衡的移動協助數據收集模式［J］.軟件學報，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簡單固定軌跡的機會路由算法，算法使用改進的機會路由策略，適用于由移動節點組成的延遲容忍無線傳感器網絡。數據傳輸采用機會路由策略，每次傳輸數據包，在包內記錄所轉發層數，通過自適應算法，動態調整從任意位置將數據發送至Sink路線所需轉發層數。實驗結果驗證算法的有效性。

徐飚（1988～），男，河南鄭州人，在讀研究生，研究方向為無線傳感器網絡、云計算

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.