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

高彩霞，祁昌平

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

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

高彩霞，祁昌平

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

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

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

0 引言

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

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

1 相關(guān)研究

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

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

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

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

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

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

3)全部節(jié)點(diǎn)均不需要人工維護(hù).

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

5)全部節(jié)點(diǎn)的運(yùn)行時(shí)鐘保持同步.

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

圖1 節(jié)點(diǎn)的運(yùn)行方式Fig 1The operation mode of node

2.2 通信模型

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

(1)

接收長(zhǎng)度為nbit的消息消耗的能量為[7]

(2)

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

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

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

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

(3)

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

3.2 鄰居變化率

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

(4)

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

(5)

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

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

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

(6)

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

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

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

(7)

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

(8)

其中Pth為閾值.

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

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

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

為了測(cè)試文中提出的轉(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編程，進(jìn)行仿真實(shí)驗(yàn).同時(shí)為了文中算法結(jié)果具有可比性，選擇SW,Binary spray and wait(BSW)和Epidemic算法進(jìn)行對(duì)比，并選擇傳輸成功率、平均延遲、開銷率作為算法的評(píng)價(jià)標(biāo)準(zhǔn).仿真參數(shù)設(shè)置見表1.

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

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

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

4.2 結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

為了更加充分利用機(jī)會(huì)網(wǎng)絡(luò)的能量，有效延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間，提高數(shù)據(jù)傳輸成功率，提出了一種基于節(jié)點(diǎn)差異性的機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法.該算法充分考慮節(jié)點(diǎn)的剩余能量和鄰居變化率，以及自適應(yīng)調(diào)節(jié)不同鄰居相似度下的轉(zhuǎn)發(fā)條件.仿真驗(yàn)證實(shí)驗(yàn)結(jié)果表明，與其他機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)算法相比，文中算法不僅提高了網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)某晒β?，減少了網(wǎng)絡(luò)傳輸延遲，并且大幅度降低了節(jié)點(diǎn)間的轉(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] 楊波,王雷.高性能的機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)機(jī)制EH-EC[J]. 計(jì)算機(jī)應(yīng)用,2010,20(12):3180-3184.

[5] 錢景輝.一種機(jī)會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)轉(zhuǎn)發(fā)策略的改進(jìn)[J]. 微電子學(xué)與計(jì)算機(jī),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] 劉唐,彭艦,王建忠,等.延遲容忍移動(dòng)傳感器網(wǎng)絡(luò)中基于節(jié)點(diǎn)優(yōu)先級(jí)的數(shù)據(jù)轉(zhuǎn)發(fā)策略[J]. 計(jì)算機(jī)科學(xué),2011,38(3):140-146.

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

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

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

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

[12] 舒堅(jiān),楊世偉,劉琳嵐.機(jī)會(huì)網(wǎng)絡(luò)中的自適應(yīng)轉(zhuǎn)發(fā)控制算法[J]. 計(jì)算機(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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61173124)

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

TP 393.01

A

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