高彩霞，祁昌平

(河西學(xué)院信息技術(shù)與傳媒學(xué)院 ,甘肅張掖 734000)

基于節(jié)點差異性的機會網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法

高彩霞，祁昌平

(河西學(xué)院信息技術(shù)與傳媒學(xué)院 ,甘肅張掖 734000)

為了提高機會網(wǎng)絡(luò)傳輸成功率，降低傳輸開銷，提出了一種基于節(jié)點差異性的機會網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法.選擇剩余能量大、鄰居更新速度快的節(jié)點作為中繼節(jié)點，根據(jù)節(jié)點對的鄰居相似度自適應(yīng)調(diào)節(jié)閾值，以滿足不同網(wǎng)絡(luò)環(huán)境下的轉(zhuǎn)發(fā)要求.仿真實驗表明，此算法與其他算法相比，在較低的傳輸延遲下大大提高了傳輸?shù)某晒β?，降低了網(wǎng)絡(luò)傳輸開銷.

機會網(wǎng)絡(luò)；鄰居變化率；傳輸性能；自適應(yīng)轉(zhuǎn)發(fā)

0 引言

機會網(wǎng)絡(luò)是一種通過節(jié)點移動來實現(xiàn)的延遲容忍網(wǎng)絡(luò).相對于傳統(tǒng)無線網(wǎng)絡(luò),機會網(wǎng)絡(luò)的規(guī)模和節(jié)點初始位置無法預(yù)先設(shè)置，以“存儲-攜帶-轉(zhuǎn)發(fā)”模式傳輸信息.由于機會網(wǎng)絡(luò)可以處理網(wǎng)絡(luò)分裂、時延等傳統(tǒng)網(wǎng)絡(luò)不能解決的難題，在通信基礎(chǔ)設(shè)施缺乏、網(wǎng)絡(luò)環(huán)境惡劣等場合得到了廣泛的應(yīng)用[1].然而在機會網(wǎng)絡(luò)應(yīng)用過程中，網(wǎng)絡(luò)被分割成不連通的子區(qū)域，數(shù)據(jù)通信利用節(jié)點移動帶來的相遇機會來實現(xiàn)，因此怎樣選擇最優(yōu)節(jié)點進行數(shù)據(jù)的轉(zhuǎn)發(fā)，成為機會網(wǎng)絡(luò)研究中的難點和熱點[2].

為了提高數(shù)據(jù)傳輸成功率，文中提出了一種基于節(jié)點差異性的機會網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法.首先考慮節(jié)點的剩余能量和鄰居變化率，選擇剩余能量大、鄰居更新快的節(jié)點作為中繼節(jié)點；然后根據(jù)節(jié)點對的鄰居相似度調(diào)節(jié)閾值的大小，控制不同節(jié)點傳輸性能和不同網(wǎng)絡(luò)環(huán)境下的轉(zhuǎn)發(fā)條件，實現(xiàn)自適應(yīng)轉(zhuǎn)發(fā)決策;最后進行仿真實驗，測試算法的性能.

1 相關(guān)研究

針對機會網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)問題，國內(nèi)外學(xué)者進行了大量而深入的研究，提出許多有效的數(shù)據(jù)轉(zhuǎn)發(fā)算法[3].最為原始也最為簡單的算法為直接傳輸(Direct transmission)算法，該算法具有消耗小等優(yōu)點，但是僅當(dāng)節(jié)點移動到匯聚點的通信范圍內(nèi)，才能進行數(shù)據(jù)有效傳輸，且存在延遲大、傳輸成功率低等不足，限制其應(yīng)用范圍[4].之后有學(xué)者提出基于洪泛理論(flooding)的機會網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法，較好地降低了延遲，提高了數(shù)據(jù)傳輸成功率，但是存在網(wǎng)絡(luò)資源消耗和丟包現(xiàn)象十分嚴(yán)重的缺點[5].文獻[6]提出了一種基于RED策略的數(shù)據(jù)轉(zhuǎn)發(fā)算法，通過消息傳輸?shù)陌l(fā)生與否計算數(shù)據(jù)傳輸概率，并根據(jù)節(jié)點當(dāng)前傳輸概率對參數(shù)進行編碼，有效提高了數(shù)據(jù)傳輸?shù)某晒β?，但是如何計算參?shù)全憑經(jīng)驗，具有較強的主觀性和盲目性.為了減少網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)延遲，降低網(wǎng)絡(luò)的開銷，有學(xué)者提出了SW(spray and wait)算法，其數(shù)據(jù)傳輸效率與消息副本數(shù)量密切相關(guān)，當(dāng)副本規(guī)模較大時，延遲小，傳輸成功率高，但是網(wǎng)絡(luò)開銷比較大[7].針對SW算法存在的不足，許多學(xué)者對其進行改進，提出一些改進的SW算法，如SF(spray and focus)算法.相對于SW算法，SF算法提高了機會網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)的性能，但是該轉(zhuǎn)發(fā)方式缺乏靈活性，不能自適應(yīng)不同機會網(wǎng)絡(luò)的傳輸要求[8].文獻[9]提出了基于鄰居節(jié)點數(shù)目的效用值閾值自適應(yīng)調(diào)整算法，但僅考慮相遇節(jié)點數(shù)目變化，難以準(zhǔn)確描述機會網(wǎng)絡(luò)傳輸?shù)膶嶋H變化狀況.文獻[10]提出了一種基于節(jié)點性能的機會網(wǎng)絡(luò)自適應(yīng)轉(zhuǎn)發(fā)算法.

2 網(wǎng)絡(luò)模型與通信模型

2.1 網(wǎng)絡(luò)模型

設(shè)多個節(jié)點隨機分布在一個N×N的正方形區(qū)域內(nèi)，該傳感器網(wǎng)絡(luò)的性質(zhì)為：

1)全部機會網(wǎng)絡(luò)節(jié)點采用Random waypoint運動規(guī)律，該運動規(guī)律的思想為：在N×N的正方形區(qū)域內(nèi)，節(jié)點隨機選擇起始點S和目的點D，節(jié)點的運動速度屬于區(qū)間[Vmin,Vmax],節(jié)點勻速地從點S向點D作直線運行，在D處選取暫停時間，暫停時間屬于區(qū)間[Tmin,Tmax],并且在該位置節(jié)點處于靜止?fàn)顟B(tài),從而完成一次運動過程.然后將點D作為下次運動的起始點S，進入下一輪運動，不斷重復(fù).

2)以基站作為參考標(biāo)準(zhǔn)，對全部匯聚點進行部署，一旦部署后，匯聚點就不能再移動[11].

3)全部節(jié)點均不需要人工維護.

4)各節(jié)點當(dāng)前位置及運動速率通過全球定位系統(tǒng)(Global positioning system， GPS)確定.

5)全部節(jié)點的運行時鐘保持同步.

網(wǎng)絡(luò)模型如圖1所示.

圖1 節(jié)點的運行方式Fig 1The operation mode of node

2.2 通信模型

根據(jù)傳輸距離，使用自由空間和多徑衰落這兩種信道模型.如果通信距離小于某個閾值，使用自由空間信道模型；否則，使用多徑衰落信道模型[12].發(fā)送長度為kbit、距離為d的消息消耗的能量為[7]

(1)

接收長度為nbit的消息消耗的能量為[7]

(2)

其中eRx為接收1bit消息消耗的能量.

3 轉(zhuǎn)發(fā)算法

3.1 節(jié)點的剩余能量

一個節(jié)點的剩余能量越多，它將消息轉(zhuǎn)發(fā)到目標(biāo)節(jié)點的成功率就越高.由于能量百分比難以對節(jié)點當(dāng)前的能量狀態(tài)進行準(zhǔn)確描述，因此對節(jié)點的剩余能量Ei進行歸一化處理[8]:

(3)

其中，uE為節(jié)點i的剩余能量率；Ej是相遇節(jié)點j的剩余能量.

3.2 鄰居變化率

一個節(jié)點的鄰居變化率越高，該節(jié)點在一定時間內(nèi)與其他節(jié)點相遇的概率就越大.設(shè)Ni為節(jié)點i的鄰居變化率，則[12]

(4)

其中，t和told為當(dāng)前時刻和上一次更新鄰居節(jié)點列表的時刻；Ni(t)和Ni(told)分別表示節(jié)點i的當(dāng)前鄰居節(jié)點列表和上一次的鄰居節(jié)點列表.同樣，對Ni進行歸一化處理[8]:

(5)

其中，uN為節(jié)點i的鄰居變化率比率；Nj是相遇節(jié)點j的鄰居變化率.

3.3 數(shù)據(jù)傳輸性能

節(jié)點傳輸能力的優(yōu)劣主要通過剩余能量和鄰居變化率來估計.一個節(jié)點的剩余能量和鄰居變化率越高，該節(jié)點的數(shù)據(jù)傳輸能力就越強.節(jié)點i的傳輸性能為[10]

(6)

其中ω表示權(quán)重值，其值大小在0～1.

3.4 轉(zhuǎn)發(fā)控制因子

在機會網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)過程，節(jié)點性能越優(yōu)異，它可以承擔(dān)的傳輸任務(wù)就越多.根據(jù)該思想，當(dāng)兩個節(jié)點i與j相遇時，可以得到Pi和Pj，如果Pj>Pi，那么節(jié)點j的傳輸性能更優(yōu)，但這時不一定表示節(jié)點i應(yīng)該轉(zhuǎn)發(fā)消息包給節(jié)點j.文中數(shù)據(jù)轉(zhuǎn)發(fā)算法參考過鄰居相似程度對閾值進行自適應(yīng)調(diào)整，提高數(shù)據(jù)轉(zhuǎn)發(fā)的成功率.設(shè)Di,j為節(jié)點i相對于節(jié)點j的閾值控制因子，則有[9]

(7)

在消息轉(zhuǎn)發(fā)中，節(jié)點i(攜帶消息包)與節(jié)點j相遇，若滿足(8)式的條件，則節(jié)點i將該消息轉(zhuǎn)發(fā)給節(jié)點j;否則，繼續(xù)等待相遇節(jié)點.

(8)

其中Pth為閾值.

綜合上述可知，基于節(jié)點差異的機會網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法的工作流程如圖2.

4 仿真實驗

4.1 仿真環(huán)境及參數(shù)設(shè)置

為了測試文中提出的轉(zhuǎn)發(fā)算法的有效性和優(yōu)越性，在Windows XP操作系統(tǒng)，Intel(R) Core(TM) i3-2120 2.8 GHz CPU，4 GB RAM環(huán)境下，采用Matlab 2012編程，進行仿真實驗.同時為了文中算法結(jié)果具有可比性，選擇SW,Binary spray and wait(BSW)和Epidemic算法進行對比，并選擇傳輸成功率、平均延遲、開銷率作為算法的評價標(biāo)準(zhǔn).仿真參數(shù)設(shè)置見表1.

圖2 轉(zhuǎn)發(fā)算法工作流程Fig 2The working process of the forward algorithm

表1 仿真參數(shù)設(shè)置

圖3 不同算法的傳輸成功率對比Fig 3 The comparison of transmission rate of the different algorithms

4.2 結(jié)果與分析

4.2.1 傳輸成功率比較 在不同節(jié)點密度條件下，不同算法的機會網(wǎng)絡(luò)數(shù)據(jù)傳輸成功率如圖3所示.從圖3可以看出:

1)在相同節(jié)點密度條件下，SW和BSW算法的數(shù)據(jù)傳輸成功率高于Epidemic算法，這主要由于SW和BSW算法基數(shù)據(jù)傳輸效率與消息副本數(shù)量密切相關(guān)，當(dāng)副本規(guī)模較大時，其延遲小，傳輸成功率高.

2)相對于SW，BSW和Epidemic算法，文中算法的傳輸成功率明顯提高.例如，節(jié)點數(shù)為150時，文中算法成功率為0.55，SW算法為0.4，BSW算法為0.43，而Epidemic算法只為0.25，這主要由于文中算法選擇剩余能量大、鄰居更新快的節(jié)點作為中繼節(jié)點，并根據(jù)鄰居相似度動態(tài)調(diào)節(jié)閾值，以滿足不同網(wǎng)絡(luò)環(huán)境下的轉(zhuǎn)發(fā)條件，從而提高了傳輸成功率.

4.2.2 網(wǎng)絡(luò)平均延遲比較 在不同時間條件下，不同算法的平均延遲如圖4所示.從圖4可以看出:

1)相對于Epidemic算法，SW和BSW算法的網(wǎng)絡(luò)平均延遲得到大幅度改善，具有更優(yōu)的機會網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)性能，提高了數(shù)據(jù)傳輸效率和速度.

2)相對于SW,BSW算法，文中算法的網(wǎng)絡(luò)平均延遲基本持平，相差不大，平均延遲沒有得到較好改善.但是隨著時間增加，所有算法由于泛洪機制造成的網(wǎng)絡(luò)擁塞，導(dǎo)致消息包不能到達目標(biāo)節(jié)點，從而導(dǎo)致機會網(wǎng)絡(luò)傳輸平均延遲比較大.

圖4 不同算法的網(wǎng)絡(luò)傳輸平均延遲比較Fig 4 The comparison of transmission network average delay of different algorithms

4.2.3 開銷率比較 在不同節(jié)點條件下，不同算法的網(wǎng)絡(luò)開銷率如圖5所示.從圖5可以看出:

1)在所有算法中，Epidemic算法開銷率最大，是其他算法的近10倍，這主要由于Epidemic算法需要大量的額外開銷，導(dǎo)致網(wǎng)絡(luò)資源浪費十分嚴(yán)重.

2)相對于SW，BSW算法，文中算法在開銷率方面優(yōu)勢顯著，比SW和BSW算法減少了約20%開銷，這主要由于文中算法有目的地選擇傳輸能力強的中繼節(jié)點，并自適應(yīng)控制轉(zhuǎn)發(fā)條件，減少了盲目轉(zhuǎn)發(fā)造成的資源浪費.

圖5 不同算法的網(wǎng)絡(luò)開銷率比較Fig 5 The comparison of network overhead rate of different algorithms

5 結(jié)束語

為了更加充分利用機會網(wǎng)絡(luò)的能量，有效延長網(wǎng)絡(luò)生存時間，提高數(shù)據(jù)傳輸成功率，提出了一種基于節(jié)點差異性的機會網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法.該算法充分考慮節(jié)點的剩余能量和鄰居變化率，以及自適應(yīng)調(diào)節(jié)不同鄰居相似度下的轉(zhuǎn)發(fā)條件.仿真驗證實驗結(jié)果表明，與其他機會網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法相比，文中算法不僅提高了網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)某晒β?，減少了網(wǎng)絡(luò)傳輸延遲，并且大幅度降低了節(jié)點間的轉(zhuǎn)發(fā)次數(shù)，網(wǎng)絡(luò)傳輸開銷急劇減少.

[1] PELUSI L,PASSARELLA A,CONTI M.Opportunistic networking:Data forwarding in disconnected mobile Ad hoc networks[J].CommunicationsMagazine,2006,44(11):134-141.

[2] CHEN L，YU C，SUN T，et al.A hybrid routing approach for opportunistic networks[C]//Proceedingsofthe2006SIGCOMMWorkshoponChallengedNetworks.Pisa:ACM，2006:213-220.

[3] LEGUAY J，F(xiàn)RIEDMAN T，CONAN V.DTN routing in a mobility pattern space[C]//Proceedingsofthe2005ACMSIGCOMMWorkshoponDelayTolerantNetworking.Philadelphia:ACM，2005:276-283.

[4] 楊波,王雷.高性能的機會網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)機制EH-EC[J]. 計算機應(yīng)用,2010,20(12):3180-3184.

[5] 錢景輝.一種機會網(wǎng)絡(luò)中節(jié)點轉(zhuǎn)發(fā)策略的改進[J]. 微電子學(xué)與計算機,2013,30(1):5-8.

[6] GUPTA B,GHOSH K,DUTTA D,et al.Broadcasting in complete and incomplete star interconnection networks [J].InternationalJournalofComputerSystemScienceandEngineering,2001,4(2):205-21.

[7] 劉唐,彭艦,王建忠,等.延遲容忍移動傳感器網(wǎng)絡(luò)中基于節(jié)點優(yōu)先級的數(shù)據(jù)轉(zhuǎn)發(fā)策略[J]. 計算機科學(xué),2011,38(3):140-146.

[8] 龔丁海.機會網(wǎng)絡(luò)中轉(zhuǎn)發(fā)機制的研究[J]. 河池學(xué)院學(xué)報,2011,31(2):49-51.

[9] 孫利民,熊永平,馬建.機會移動傳感器網(wǎng)絡(luò)中的自適應(yīng)數(shù)據(jù)收集機制[J].通信學(xué)報,2008,29(11):186-193.

[10] 周航,牛建偉,孫利民,等.機會網(wǎng)絡(luò)中自適應(yīng)多跳多拷貝傳輸算法[J].計算機科學(xué),2008,35(11):167-170.

[11] 孫踐知,劉乃瑞,張迎新,等.機會網(wǎng)絡(luò)典型路由算法性能分析[J]. 計算機工程,2011,37(16):86-89.

[12] 舒堅,楊世偉,劉琳嵐.機會網(wǎng)絡(luò)中的自適應(yīng)轉(zhuǎn)發(fā)控制算法[J]. 計算機應(yīng)用研究,2011,28(6):2336-2338.

(責(zé)任編輯 惠松騏)

Data transmission algorithm of opportunistic networks based on nodes difference

GAO Cai-xia,QI Chang-ping

(College of Information Technology and Media，Hexi University，Zhangye 734000，Gansu，China)

In order to improve the success rate of network transmission,reduce transport costs,a novel data transmission algorithm of opportunistic networks based on nodes' difference is proposed.Firstly,the node residual energy and neighbor update speed is selected as a relay node;and then the threshold is adaptively adjusted according to neighbor similarity node to meet the forwarding requirements under the different network environment.The simulation results show that this proposed algorithm not only has improved the network data transmission probability and reduced the delay of network transmission,and greatly reduce the transmission number of nodes and sharply reduce the network cost compared with other opportunistic network data forwarding algorithms.

opportunistic network;change rate of neighbors;transmission performance;adaptive transmission

2014-10-08;修改稿收到日期:2015-01-25

國家自然科學(xué)基金資助項目(61173124)

高彩霞(1976—)，女，甘肅張掖人，講師，碩士.主要研究方向為數(shù)據(jù)挖掘與人工智能. E-mail:bixiyadianna@foxmail.com

TP 393.01

A

1001-988Ⅹ(2015)04-0042-04