文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2016.09.023
中文引用格式： 袁芬，陶琳，徐從富，等. 自適應選擇gossiping概率的多跳網(wǎng)絡數(shù)據(jù)廣播[J].電子技術應用，2016，42(9)：87-90，94.
英文引用格式： Yuan Fen，Tao Lin，Xu Congfu，et al. Multi-hop network data broadcast protocol based on adaptive selection gossiping probability[J].Application of Electronic Technique，2016，42(9)：87-90，94.
0 引言
移動Ad Hoc無線網(wǎng)絡是由共享無線介質(zhì)的移動節(jié)點組成，移動節(jié)點能夠根據(jù)需要構建任意的拓撲結構，不需要固定的基礎設施及中央管理系統(tǒng)的加入[1-2]。由于移動節(jié)點隨機分布，兩個無法直接進行通信的節(jié)點還能夠通過其他節(jié)點協(xié)作進行分組轉發(fā)[3-4]，不依賴于現(xiàn)有的網(wǎng)絡通信設施，具有一定的獨立性，適合復雜環(huán)境通信及災難救助等應用[5-6]。文獻[7]提出Ad Hoc網(wǎng)絡中一種鏈路負載均衡的節(jié)能路由協(xié)議，協(xié)議通過考慮網(wǎng)絡中節(jié)點生存時間和節(jié)點間鏈路通信效率兩個方面因素，重新定義和計算鏈路性能,以達到優(yōu)化路由選擇的效果的目的。文獻[8]提出一種基于平均場均衡的Ad Hoc網(wǎng)絡路由協(xié)議，要求每個節(jié)點利用所有其他節(jié)點的信息來分析自己的最優(yōu)策略,而不需要知道每一個局中人的信息,并且在足夠大的局中人數(shù)目情況下性能更加近似馬爾科夫均衡，在節(jié)點密集的無線自組織網(wǎng)絡中路由協(xié)議在包投遞率、時延和歸一化開銷方面獲得了比較好的效果。文獻[9]提出TOAR：傳輸感知的機會Ad Hoc路由協(xié)議，該協(xié)議通過數(shù)學模型求解OR協(xié)議產(chǎn)生重復數(shù)據(jù)包的總數(shù)量，采用樹拓撲選擇轉發(fā)節(jié)點的優(yōu)先級次序，盡可能得減少數(shù)據(jù)包重傳數(shù)量。文獻[10]提出PSR：一個輕量級的移動Ad Hoc網(wǎng)絡主動源路由協(xié)議，該協(xié)議基于鏈路狀態(tài)信息、距離信息對傳輸路由進行優(yōu)化，使源節(jié)點選擇開銷更小的數(shù)據(jù)傳輸鏈路。
1 自適應選擇gossiping概率方法
Gossiping路由協(xié)議是對Flooding路由協(xié)議的改進，使用隨機原則，節(jié)點發(fā)送數(shù)據(jù)時不再采用廣播形式，而是根據(jù)概率隨機轉發(fā)數(shù)據(jù)包到鄰居節(jié)點，接著該鄰居節(jié)點再以相同的方式向其鄰近節(jié)點轉發(fā)該數(shù)據(jù)包，直到數(shù)據(jù)包到達接收終端[11-12]。本文提出的方法旨在減少冗余路由數(shù)據(jù)包，減少網(wǎng)絡整體開銷，節(jié)省能源消耗。
假設網(wǎng)絡場景為移動節(jié)點隨機分布的自組織網(wǎng)絡，該Ad Hoc無線通信網(wǎng)絡的節(jié)點共享一個無線電信道，節(jié)點可以通過無線信道在傳輸半徑r范圍內(nèi)互相通信，并且可以通過多跳路徑的方式將信息傳輸給較遠的節(jié)點，除非某一節(jié)點不在其他任何節(jié)點的通信范圍內(nèi)，這種情況該節(jié)點則無法與相鄰節(jié)點交換信息。由于所有節(jié)點都均勻且獨立地分布于網(wǎng)絡區(qū)域中，在范圍r內(nèi)一個節(jié)點找到n個鄰居節(jié)點的概率可以用二項概率密度函數(shù)來定義：
其中，V表示網(wǎng)絡節(jié)點的總數(shù)量，S表示網(wǎng)絡總覆蓋面積。
由于
，本文采用泊松分布均值
可以將式(1)轉化為：
一個節(jié)點在其傳輸范圍r內(nèi)有至少一個相鄰節(jié)點的概率為：
因此，一個節(jié)點在其傳輸范圍內(nèi)的預期平均鄰居節(jié)點數(shù)量可以表示為：
接下來討論在該gossiping概率下鄰居轉發(fā)節(jié)點的選擇問題。
已知一個節(jié)點在其傳輸范圍內(nèi)的預期鄰居節(jié)點數(shù)量為An，采用傳統(tǒng)的廣播泛洪的方法則會傳輸與路由相關的數(shù)據(jù)包至其傳輸范圍內(nèi)的所有鄰居節(jié)點，能量開銷較大，而gossiping路由則是以隨機概率的形式傳輸數(shù)據(jù)包至鄰居節(jié)點，能量開銷小，但傳輸成功率不可靠。而本文采用自適應選擇的gossiping概率方法，則是首先排除掉無下一跳節(jié)點的鄰居節(jié)點，再根據(jù)網(wǎng)絡平均鄰居節(jié)點數(shù)與發(fā)送節(jié)點的實際鄰居節(jié)點數(shù)情況，通過自適應的概率條件傳輸數(shù)據(jù)包至鄰居節(jié)點。在節(jié)省能量開銷的同時保持傳輸成功率，是本文設計自適應選擇gossiping概率方法的目的。
式(4)已知預期平均鄰居節(jié)點數(shù)為An，本文首先定義網(wǎng)絡的自適應gossiping概率為
，則：
對于n>An的情況，如果?滋n過低，則說明總節(jié)點數(shù)量過少，總覆蓋面積過大，平均鄰居節(jié)點數(shù)量An過少，此時即使發(fā)送節(jié)點的實際鄰居節(jié)點n較多，但該發(fā)送節(jié)點的鄰居節(jié)點可能過少甚至沒有，此時路由請求信息可能會消失；如果
過高，則網(wǎng)絡在發(fā)送路由信息上存在著巨大的開銷。為了避免這種情況，提高任一個發(fā)送節(jié)點i的傳輸可靠性及減少能量開銷。本文假設發(fā)送節(jié)點i的下一跳鄰居節(jié)點集為
，且鄰居節(jié)點
，為
增加選擇能力，則表達式優(yōu)化為：
對于網(wǎng)絡的自適應選擇gossiping概率
，
表示任一個發(fā)送節(jié)點i的候選鄰居節(jié)點被選擇作為數(shù)據(jù)包轉發(fā)節(jié)點的概率，當候選鄰居節(jié)點其自身的下一跳鄰居節(jié)點集為空集時，則該候選鄰居節(jié)點將被徹底排除作為轉發(fā)節(jié)點的可能性。而
，1則是優(yōu)化了
的能量開銷問題，當且僅當該節(jié)點的實際鄰居節(jié)點數(shù)量n大于預期平均鄰居節(jié)點數(shù)量，否則自適應選擇的gossiping概率為1。
2 能耗情況分析
令V表示節(jié)點總數(shù)，n表示一個節(jié)點在其通信半徑內(nèi)的平均鄰居節(jié)點數(shù)量，Prece假設為廣播一個數(shù)據(jù)包的節(jié)點接收功率，Ptrans表示節(jié)點發(fā)射功率。對于每個節(jié)點發(fā)送的分組總數(shù)和每個節(jié)點接收的平均分組數(shù)量，分別用Ktrans和Krece表示。
采用泛洪的廣播數(shù)據(jù)方式，當節(jié)點接收到一個數(shù)據(jù)包時，它轉發(fā)n個數(shù)據(jù)包至其n個鄰居節(jié)點，因此采用泛洪的廣播數(shù)據(jù)方式的
。對應的節(jié)點能量總開銷為：
而采用gossiping概率隨機廣播的方式，則節(jié)點接收到上一個節(jié)點發(fā)送的數(shù)據(jù)包以及轉發(fā)數(shù)據(jù)包到鄰居節(jié)點是以概率性的方式，
K。對應的節(jié)點能量總開銷為：
而采用自適應選擇的gossiping概率方法進行廣播數(shù)據(jù)包，
，假設每個節(jié)點都有鄰居節(jié)點，當n>An，則對應的節(jié)點能量總開銷為：
當
，則對應的節(jié)點能量總開銷為：
則
。
3 實驗仿真及分析
在本文實驗的部分，采用的仿真模擬器為NS2，仿真實驗場景為500×500的正方形區(qū)域，網(wǎng)絡中節(jié)點數(shù)量的變化范圍為(200，800)，其中有20個為數(shù)據(jù)發(fā)送端源節(jié)點，節(jié)點的通信半徑為100 m，所有節(jié)點都隨機分布于網(wǎng)絡場景中。源節(jié)點每一秒發(fā)送一個數(shù)據(jù)包，數(shù)據(jù)包大小為512 B，其他仿真參數(shù)如表1所示。
圖1顯示了在移動節(jié)點數(shù)量變化條件下的網(wǎng)絡節(jié)點總能耗情況，gossiping路由協(xié)議只是采取概率性的鄰居節(jié)點選擇策略，網(wǎng)絡節(jié)點總能耗情況取決于gossiping概率p。p越大，總能耗越大。TOAR算法通過減少數(shù)據(jù)包傳輸達到節(jié)省能耗的目的，PSR算法則是通過傳輸鏈路優(yōu)化來節(jié)省發(fā)送數(shù)據(jù)包的開銷。本文提出的AS-gossiping算法通過使gossiping概率具有選擇能力從而避免傳輸中斷的情況，減少不必要的能量開銷，同時自適應gossiping概率也減少了在路由信息上的開銷，因此節(jié)能性能更好，相比gossiping路由協(xié)議，TOAR協(xié)議和PSR協(xié)議分別減少了32.5%、14.6%和2.1%的總能耗。
圖2顯示了在移動節(jié)點數(shù)量增多條件下的數(shù)據(jù)包平均丟失率情況，從圖中可以看出，隨著移動節(jié)點數(shù)量的增多，數(shù)據(jù)包平均丟失率減小，這是由于每個節(jié)點的平均鄰居節(jié)點數(shù)量增多，gossiping路由協(xié)議可以將同一分組數(shù)據(jù)包傳遞給更多的鄰居節(jié)點，數(shù)據(jù)包成功傳遞到目的節(jié)點的成功率大大增加。對于TOAR和PSR算法來說，則是可以選擇的下一跳節(jié)點增多，傳輸鏈路的能量效率大大提高。而本文算法數(shù)據(jù)包平均丟失率減少的原因與gossiping路由協(xié)議相同，但相比gossiping路由協(xié)議，本文算法還減少了傳輸中斷情況，因此在減少丟包率上表現(xiàn)出更好的性能。
圖3顯示了在移動節(jié)點數(shù)量增加條件下的數(shù)據(jù)包傳輸延遲情況。從圖中的仿真結果來看，gossiping路由協(xié)議的數(shù)據(jù)包延遲情況較嚴重，而所有算法的數(shù)據(jù)包延遲時間都隨著節(jié)點數(shù)量的增加而增加，這是因為每個節(jié)點的平均鄰居節(jié)點增多，而Ad Hoc網(wǎng)絡采用的是多跳傳輸方式，跳數(shù)的增加伴隨而來的是傳輸時間的增多。由于本文算法的gossiping概率考慮了節(jié)點密度，當鄰居節(jié)點越多，gossiping概率越小，相鄰較近的節(jié)點不一定被選中，因此在跳數(shù)增加上并不明顯。
4 結束語
本文提出基于對gossiping路由協(xié)議的研究，針對gossiping概率廣播信息開銷較大及傳輸中斷概率較大的情況，提出一種基于自適應選擇gossiping概率的多跳網(wǎng)絡數(shù)據(jù)廣播協(xié)議。其中自適應選擇gossiping概率方法能夠對鄰居節(jié)點進行篩選，排除可能帶來中斷鏈路的鄰居節(jié)點，減少傳輸中斷概率，提高能量效率。對候選的鄰居節(jié)點采用自適應gossiping概率進行數(shù)據(jù)包廣播，自適應gossiping概率基于發(fā)送節(jié)點實際鄰居節(jié)點數(shù)與網(wǎng)絡節(jié)點密度的對比情況而定，避免發(fā)送節(jié)點廣播過多的信息，節(jié)省廣播信息的能量開銷。
參考文獻
[1] REINA D G，TORAL S L，JOHNSON P，et al.Improving discovery phase of reactive ad hoc routing protocols using Jaccard distance[J].Journal of Supercomputing，2014，67(1)：131-152.
[2] BADENHOP C W，MULLINS B E.A black hole attack model using topology approximation for reactive ad-hoc routing protocols[J].International Journal of Security & Networks，2014，9(2)：63-77.
[3] LEE A，RA I.Performance ANALYSIS of ad hoc routing protocols based on selective forwarding node algorithms[C].2013 International Conference on Information Science and Applications(ICISA).IEEE Computer Society，2013：1-4.
[4] SHARMA R，LOBIYAL D K.Energy based proficiency analysis of ad-hoc routing protocols in wireless sensor networks[C].Computer Engineering and Applications(ICACEA)，2015 International Conference on Advances in.IEEE，2015.
[5] FRIGINAL J，ANDR?魪S D D，RUIZ J C，et al.REFRAHN： A resilience evaluation framework for ad hoc routing protocols[J].Computer Networks，2015，82(5)：114-134.
[6] ARNAUD M，CORTIER V，DELAUNE S.Modeling and verifying ad hoc routing protocols[J].Information & Computation，2014，238(3)：30-67.
[7] 韓智洋，束永安.Ad Hoc網(wǎng)絡中一種鏈路負載均衡的節(jié)能路由協(xié)議[J].計算機技術與發(fā)展，2014(1)：85-88.
[8] 張旭，錢志鴻，劉影，等.基于平均場均衡的Ad hoc網(wǎng)絡路由協(xié)議[J].哈爾濱工程大學學報，2014(4)：504-509.
[9] MAZUMDAR A P，SAIRAM A S.TOAR：transmissionaware opportunistic ad hoc routing protocol[J].Eurasip Journal on Wireless Communications & Networking，2013，2013(5)：1-19.
[10] WANG Z，CHEN Y，LI C.PSR：A lightweight proactive source routing protocol for mobile ad hoc networks[J].Vehicular Technology IEEE Transactions on，2014，63(2)：859-868.
[11] ASENSIO-MARCO C，BEFERULL-LOZANO B.Fast average gossiping under asymmetric links in WSNS[C].Signal Processing Conference(EUSIPCO)，2014 IEEE，2014：131135.
[12] LEE B，SONG H K，SUH Y，et al.Energy-efficient gossiping protocol of WSN with realtime streaming data[C].Dependable，Autonomic and Secure Computing(DASC)，2014 IEEE 12th International Conference on.IEEE，2014：219-224.