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

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

中圖分類號(hào):TP393 文獻(xiàn)標(biāo)識(shí)碼:A

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

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

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

1 傳輸概率

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

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

圖1 移動(dòng)節(jié)點(diǎn)全局分布

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

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

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

pi=1,R/d≥1

R/d,R/d<1

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

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

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

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

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

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

2 生存時(shí)間

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

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

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

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

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

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

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

T′0

=T0?

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

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

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

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

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

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

Ti=T′0(1-dpi)

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

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

T′0

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

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

算法如下:

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插入隊(duì)列----

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é)點(diǎn)----

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

14. Tj--;

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

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

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

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

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

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

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

移動(dòng)速度、計(jì)時(shí)粒度、通信半徑、隊(duì)列限度、等待時(shí)限、格子溫度范圍、初始生存時(shí)間。

(3) 性能指標(biāo)

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

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

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

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

默認(rèn)設(shè)置:

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

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

時(shí)間粒度:1 隊(duì)列限度:100

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

傳輸半徑:3 移動(dòng)速度:3

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

試驗(yàn)在保證其余默認(rèn)值的前提下,更改半徑、速度、隊(duì)列。

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

圖2 不同傳輸半徑、移動(dòng)速度、隊(duì)列長度下的效率對(duì)比

4 結(jié) 語

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

參考文獻(xià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 的增強(qiáng)型Earliest-Delivery[J].電子與信息學(xué)報(bào),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年出生,吉林白城人,四川大學(xué)應(yīng)用數(shù)學(xué)專業(yè)理學(xué)學(xué)士、電子科技大學(xué)電子科學(xué)技術(shù)研究院碩士研究生。研究方向?yàn)闊o線傳感器網(wǎng)絡(luò),無線路由、數(shù)據(jù)融合。