基于結(jié)合節(jié)點概率與消息ST的DTN傳輸策略

摘 要:在延遲容忍的移動無線網(wǎng)絡(luò)中,為確保消息,進行少副本、短延遲、少能耗的高效傳遞,選擇合適的傳輸策略至關(guān)重要。提出一種新的基于節(jié)點位置信息建立的傳輸概率機制,在消息傳遞時通過基于傳輸概率的消息生存時間進行隊列的管理、優(yōu)化。經(jīng)過仿真實驗得出數(shù)據(jù),對比現(xiàn)有的幾種方式,該策略可以在減少消息副本,縮短傳輸延遲,提高傳輸成功率等方面做到不同程度的優(yōu)化,且效果良好。

關(guān)鍵詞:延遲容忍;傳輸概率;隊列管理;生存時間

中圖分類號:TP393 文獻標識碼:A

文章編號:1004-373X(2009)21-067-04

DTN Delivery Scheme Based on Transfer Possibility and ST

SONG Jipeng

(Research Institution of Electronic Science and Technology,University of Electronic Science and Technology of China,Chengdu,610054,China)

Abstract:In delay tolerant mobile sensor network,delivery scheme is a key point for effective way that offers less copies,delay and high delivery rate.At first,a new real-time delivery possibility mechanism based location information is proposed.Using the possibility to mend the survival time of messages to send.In addition,optimizing the management of message-queue can be made.By simulation,the scheme gets higher message delivery ratio,lower copies and delivery delay.

Keywords:delay-tolerant;delivery possibility;queue managemant;survival time

0 引 言

在無線傳感器網(wǎng)絡(luò)中,被傳遞消息的生存時間(Survival Time,ST)[1]對網(wǎng)絡(luò)中傳感器能量和網(wǎng)絡(luò)帶寬的消耗影響較大。通過加入刻畫整個網(wǎng)絡(luò)延遲容忍程度的全局性變量標簽,當消息的在網(wǎng)生存時間大于該閾值時丟棄此消息。這樣做的主要目的是為了避免生存時間過大的消息繼續(xù)存留。這樣就產(chǎn)生了一個問題,當某一消息的在網(wǎng)時間已經(jīng)達到或超過閾值,但是沒有一份傳到中心節(jié)點,則會出現(xiàn)處于不同節(jié)點的該消息副本同時“自殺”,進而造成信息的丟失。問題歸結(jié)到這個全局閾值的確定問題,但無線傳感器網(wǎng)絡(luò)的動態(tài)特性和區(qū)域差距的影響使得該值既要考慮整體網(wǎng)絡(luò)狀況,又要兼顧局部區(qū)域的通信狀況,難于平衡,所以應(yīng)轉(zhuǎn)換思路,將全局的考慮下放到節(jié)點。

為了反映當前局部環(huán)境的狀況,結(jié)合對消息傳遞成功的估計,可以在消息中帶入一定量的標簽信息,但是這些新的數(shù)據(jù)會對節(jié)點消息隊列的管理以及消息通信帶來額外的負擔,為了解決這一困擾,可以沿用消息生存時間,并設(shè)其為可變量,將多種因素反映到對生存時間的動態(tài)修改上,這樣不會引入額外的開銷,且在一定程度上優(yōu)化了生存時間,進而達到優(yōu)化消息傳遞的目的。

在傳輸區(qū)域內(nèi)如何選取下一步要傳輸?shù)狞c,此前有多種方案:一方面是結(jié)合路由的直接傳輸方式[2,3],資源消耗少,但因為將傳輸?shù)南Ｍ糠旁趩我宦肪€上,由于各種因素的影響,相對成功傳輸概率不高;另一個方面是泛洪方式,向所有進入有效傳輸區(qū)域的節(jié)點發(fā)送消息副本,提高了傳輸?shù)某晒β?但帶來的網(wǎng)絡(luò)資源消耗過大,它隨傳輸階數(shù)的增多呈幾何級數(shù)增長;其余的是在這兩個極端方式間,根據(jù)不同的策略,選擇一定數(shù)量的節(jié)點進行傳輸,目的是在提高傳輸成功率和降低消耗間進行均衡,選取更佳的方案。這里采用基于傳輸概率的選取策略。

1 傳輸概率

傳輸概率指描述節(jié)點所攜帶的消息到達中心節(jié)點的可能性。在傳統(tǒng)的無線網(wǎng)絡(luò)中,節(jié)點靜止、位置固定,傳輸概率由距離Sink節(jié)點的遠近來確定。在加入了移動后,這種固定的方式就不存在了。圖1中的點B,D位于以Sink為中心的同一圓上,與中心距離相同,但是其運動方向相反,即B出圓,D進圓。單純按位置制定的傳輸概率是相同的,然而在移動的情況下,趨向中心的節(jié)點D顯然要比背離中心的節(jié)點B的傳輸可能性要大。而這是RED [4,5],RAD [6]等策略中所采取的方式。

針對僅考慮位置,而不考慮移動方向的情況,采取新的方式。根據(jù)節(jié)點運動的目的地與中心節(jié)點通信范圍的遠近來刻畫。通過夾角可知,當運動終點的角較大時,節(jié)點最終距中心較近,傳輸可能性較大,在0～180°間變化,相應(yīng)的點Destiny在距中心通信范圍+∞～0之間;當Destiny位于中心通信范圍內(nèi)時傳輸概率為1。這樣以上的問題得以解決。然而新的問題隨之而來,上面的模型是以移動的終點來代表運動方向的,沒有考慮到運動路線的整體情況,按照上面模型衡量,擁有相同的終點,其傳輸概率置為相同,但實際情況是沿途經(jīng)過中心區(qū)域的要擁有更高的傳輸可能性,模型出現(xiàn)了問題。究其原因,是將節(jié)點的運動依靠終點來衡量,而不是運動的路線,也就是考慮了終點而沒有考慮起點。

圖1 移動節(jié)點全局分布

在移動的影響下,傳輸概率的衡量方法靈活多樣,測算的公式以及策略簡繁不一。

然而,回過頭來分析移動節(jié)點,目的是以極大可能轉(zhuǎn)向中心節(jié)點而多跳的形式轉(zhuǎn)發(fā)消息。作為節(jié)點本身,已知中心位置、自身的位置、通信范圍內(nèi)的其他節(jié)點,考慮節(jié)點運動路線來衡量傳輸概率固然理想,但實際的運動與預期路線的差距往往使效果打折扣。如地形的起伏、節(jié)點間的碰撞、存在障礙物等。反觀最初的節(jié)點-中心距離的方式,因為移動而失效,現(xiàn)在將移動融合進去,將節(jié)點實時的位置反映到傳輸概率中。

下面根據(jù)上述Random Waypoint運動模型[7],以節(jié)點i為例,定義任意時刻節(jié)點i的傳輸概率pi:

pi=1,R/d≥1

R/d,R/d<1

式中:d為當前節(jié)點到Sink節(jié)點的距離;R為Sink節(jié)點的通信半徑。

當R/d≥1時,節(jié)點位于Sink通信范圍內(nèi),傳輸概率為1。

當R/d<1時,說明節(jié)點與Sink圓的接近程度偏向1,則更接近圓,反之偏離圓。

在傳輸前用當前位置更新節(jié)點傳輸概率;通過握手通信,得到鄰近節(jié)點的pi值;選擇傳輸概率較高的點傳輸消息。信息沿著趨向Sink的同心圓方向逐級傳遞。

這樣可以脫離消息傳遞對于節(jié)點移動的依賴,可以視中心節(jié)點及其傳輸范圍為中心,形成一個傳輸概率場,距離場心近的傳輸概率大,反之則小。

這一方式避免了不考慮運動情況的模型,也避免了只考慮移動終點的偏頗,實現(xiàn)上也簡便易行。在以消息傳遞為最終目標的運動中,通過節(jié)點位置定義的傳輸概率可以優(yōu)化消息的傳遞。在這一模型下,消息沿著傳輸概率遞增的節(jié)點路徑進行多跳傳輸,減少了副本數(shù)量,提高了傳輸效率。

2 生存時間

設(shè)消息M中的生存時間變量為T0,所在節(jié)點為Q,節(jié)點的傳輸概率為Qp,包括通信范圍內(nèi)所有節(jié)點。經(jīng)過基于傳輸概率的選取策略選定將要傳輸?shù)狞c,不妨設(shè)這n個節(jié)點為Xi(i∈[1,n])以及節(jié)點各自的傳輸概率pi,傳輸?shù)絥個節(jié)點的消息副本為Mi,生存時間為Ti。下面所要做的是在完成消息傳遞的同時,分別設(shè)置發(fā)送、接收的n+1個節(jié)點消息的生存時間。

研究發(fā)送節(jié)點消息:

(1) 當傳出消息副本數(shù)量n增多時,成功傳輸?shù)母怕示痛?消息的在網(wǎng)生存時間相應(yīng)減少。

(2) 當接收節(jié)點本身的傳輸概率較大時,成功傳輸?shù)母怕示痛?可以減少生存時間。

(3) 當接收節(jié)點相對發(fā)送節(jié)點傳輸概率的梯度較大時,意味著消息向目標傳輸?shù)呐郎俣燃涌?需要減少生存時間。

總地來說,消息的傳輸過程是所經(jīng)歷過節(jié)點的傳輸概率嚴格單調(diào)遞增,生存時間嚴格單調(diào)遞增。

綜合以上各因素,進行線性化,可得出發(fā)送節(jié)點生存時間刷新公式:

T′0

=T0?

從副本數(shù)、接收節(jié)點傳輸概率、消息傳輸梯度等方面刻畫了對生存時間的影響,這些待定系數(shù)的權(quán)重需要模擬真實環(huán)境,在分析全局數(shù)據(jù)后,進行最佳逼近,此處暫定為1∶2。

研究接收節(jié)點消息:

(1) 由于消息的ST隨節(jié)點的推移呈單調(diào)遞增趨勢,所以接收節(jié)點的ST要嚴格小于上一節(jié)點的ST值。

(2) 接收節(jié)點各自的傳輸概率不同,所接收消息的ST值也應(yīng)反映這種差異性,即傳輸概率大的ST要相對小。

(3) 隨著傳輸概率的遞增,消息隊列中的消息數(shù)也遞增,而隊列的長度受制于硬件的設(shè)計,已經(jīng)先天固定。在這一逐級的累積效應(yīng)下,要對隊列進行頻繁的出入管理,但此處消息又相對重要,因此要通過ST值的設(shè)定權(quán)衡處理。將節(jié)點累計反映到ST中。

在各種因素下,接收節(jié)點副本消息ST設(shè)置公式為:

Ti=T′0(1-dpi)

通過對上一節(jié)點、本節(jié)點傳輸概率的累計效應(yīng)刷新本地消息的生存時間。

在接收節(jié)點得到的消息副本后,要將該副本插入已有的消息隊列中。這樣要選擇一方(發(fā)/收)設(shè)置副本的生存時間。一方面,此處的生存時間來源于發(fā)送節(jié)點,繼承自已經(jīng)重置后的

T′0

;另一方面,由于節(jié)點本身傳輸概率的差異,同一消息發(fā)往不同節(jié)點副本的ST值不盡相同。

綜合考慮后,采取的策略為發(fā)出方將更新ST后的消息復制n份,分別發(fā)送到n個接收節(jié)點。接收節(jié)點再將該副本消息結(jié)合自身的特征對ST進行刷新重置,之后插入消息隊列中進行管理。

算法如下:

1. if (Receiving a new message i from other node)

2. {Ti = T0-de?pi-e?mi;

3. mi++;

4. insert into message queue of this node;

5. }----接受消息副本更新ST插入隊列----

6.. if (Sending the copies of the messages MSG to nodes Xi which i∈[1,n])

7. {T′0=T0?

8. for(every int i∈[1,n])

9.{

10.send MSGi to node Xi;

11.}

12. }----發(fā)送消息到選中節(jié)點----

13. for (every j in the queue of node i )

14. Tj--;

15.----根據(jù)本地時鐘更新隊列中消息ST值----

3 仿真設(shè)定與性能衡量

3.1 參數(shù)設(shè)置

根據(jù)DTN網(wǎng)絡(luò)的結(jié)構(gòu)[10]特征,設(shè)計仿真實驗,相關(guān)主要參數(shù)如下:

(1) 場景環(huán)境

在200×200的正方形區(qū)域內(nèi),劃分20×20的100個格子作為獨立區(qū)域;每格子在系統(tǒng)初始化時,都隨機產(chǎn)生一定溫度范圍內(nèi)的初始溫度;隨機散布傳感器節(jié)點于大正方形區(qū)域內(nèi);Sink節(jié)點位于區(qū)域中心;在設(shè)定的仿真時間內(nèi)節(jié)點按照waypoint方式移動,并進行節(jié)點通信;當仿真計數(shù)歸零時停止運動,進行數(shù)據(jù)的統(tǒng)計與分析得出結(jié)果。

(2) 涉及到參數(shù)

移動速度、計時粒度、通信半徑、隊列限度、等待時限、格子溫度范圍、初始生存時間。

(3) 性能指標

傳輸效率:最終到達中心節(jié)點的消息占區(qū)域產(chǎn)生消息的百分率。

副本數(shù):平均每條消息被復制的數(shù)目。

平均延遲:首個到達中心節(jié)點的消息(或其副本)傳遞的時間(從產(chǎn)生到抵達中心)。

3.2 數(shù)據(jù)與繪圖

默認設(shè)置:

區(qū)域:200×200區(qū)域劃分:10×10

區(qū)域溫度:0～20初始生存時間:100

時間粒度:1 隊列限度:100

節(jié)點數(shù):100 中心節(jié)點:(100,100)

傳輸半徑:3 移動速度:3

FAD的FT門限:0.8 FAD的a:0.5

試驗在保證其余默認值的前提下,更改半徑、速度、隊列。

數(shù)據(jù)與繪圖如圖2所示。

圖2 不同傳輸半徑、移動速度、隊列長度下的效率對比

4 結(jié) 語

與傳統(tǒng)泛洪、直接傳輸和FAD方法相比,新的策略主要由基于傳輸概率的傳遞策略以及基于生存時間和信息融合的隊列管理組成,經(jīng)過對比試驗,在效率與穩(wěn)定性方面有優(yōu)良的表現(xiàn)。提高了傳輸率,降低了整體通訊負擔,優(yōu)化了節(jié)點消息的管理,在一定程度上降低了消息傳遞對于節(jié)點的信息處理能力的依賴。但該策略有待于在實踐中,尤其是在能量消耗、復雜環(huán)境等方面作進一步檢驗。

參考文獻

[1]

Wang Yu.Replication-Based Efficient Data Delivery Scheme (RED) for Delay/Fault-Tolerant Mobile Sensor Network (DFT-MSN)[A].Proc.of Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops.Pisa: IEEE Press,2006:485-489.

[2]Wang Yu,Dang H.Analytic Study of Delay/Fault-Tolerant Mobile Sensor Networks (DFT-MSN′s)[R].Tech.Report,Lafayette: CACS,University of Louisiana at Lafayette,2006.

[3]Mihaela Cardei,Yang Shuhui,Wu Jie.Algorithms for Fault-Tolerant Topology in Heterogeneous[J].Wireless Sensor Networks IEEE Trans.on Parallel and Distributed Systems,2008,19(4):545-558.

[4]Tracy Camp,Jeff Boleng,Vanessa Davies.A Survey of Mobility Models for Ad Hoc Network [J].Wireless Communication & Mobile Computing (WCMC): Special Issue on Mobile Ad Hoc Networking :Research,Trends and Applications,2002,2(5):483-502.

[6]周曉波,盧漢成,李津生,等.AED: 一種用于DTN 的增強型Earliest-Delivery[J].電子與信息學報,2007,29(8):1 956-1 960.

[5]Wang Yu,Wu Hongyi,Dang Ha,et al.Analytic,Simulation,and Empirical Evaluation of Delay/Fault-Tolerant Mobile Sensor Networks[J].IEEE Trans.on Wireless Communications,2007,6(9):3 287-3 296.

[7]Wang Yu,Wu Hongyi.The DFT-MSN: The Delay/Fault-Tolerant Mobile Sensor Network for Pervasive Information Gathering.25th IEEE International Conference on Computer Communications.2006:1-12.

[8]Zhou Xiaobo,Zhou Jian,Lu Hancheng,et al.Analysis of Delay Model in DTN[J].Application Research of Computers,2008,6:960-966.

[9]Vinton Cerf,Scott Burleigh,Adrian Hooke,et al.Deley-Tolorant Network Architecture[Z].DTN Research Group Internet Draft,2003:5-15.

[10]Michael Demmer,Eric Brewer,Kevin Fall,et al.Intel Implementing Delay Tolerant Networking [EB/OL].http://citeseerx.ist.psu.edu/legacymapper?did=725204.2007.10

作者簡介 宋吉鵬 男,1982年出生,吉林白城人,四川大學應(yīng)用數(shù)學專業(yè)理學學士、電子科技大學電子科學技術(shù)研究院碩士研究生。研究方向為無線傳感器網(wǎng)絡(luò),無線路由、數(shù)據(jù)融合。