《電子技術應用》
您所在的位置：首頁 > 通信與網絡 > 設計應用 > 自適應選擇gossiping概率的多跳網絡數(shù)據廣播
自適應選擇gossiping概率的多跳網絡數(shù)據廣播
2016年電子技術應用第9期
袁 芬1，陶 琳2，徐從富3，魏霖靜4
1.浙江長征職業(yè)技術學院 計算機與信息技術系，浙江 杭州310023； 2.河南工業(yè)職業(yè)技術學院 電子信息工程系，河南 南陽473000； 3.浙江大學 計算機科學與技術學院，浙江 杭州310027；4.甘肅農業(yè)大學 信息科學技術學院，甘肅 蘭州730070
摘要： 移動Ad Hoc無線網絡節(jié)點在廣播報文信息時占用大量的網絡資源，且廣播信息的能量開銷較大。為了解決這些問題，提出一種基于自適應選擇gossiping概率的多跳網絡數(shù)據廣播協(xié)議。該協(xié)議首先基于網絡節(jié)點密度分布情況及節(jié)點平均鄰居數(shù)量來定義gossiping概率，減少廣播信息的開銷，再為自適應gossiping概率加入選擇能力，從候選鄰居節(jié)點中排除會帶來傳輸中斷情況的節(jié)點，避免能量損失。實驗仿真結果表明，該協(xié)議相比較gossiping路由協(xié)議、傳輸感知的機會Ad Hoc路由協(xié)議和輕量級的移動Ad Hoc網絡主動源路由協(xié)議，網絡總能耗分別減少了32.5%、14.6%和2.1%，并且在降低數(shù)據包丟失率和減少數(shù)據包傳輸延遲上表現(xiàn)出較好的效果。
中圖分類號： TN915；TP393
文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2016.09.023
中文引用格式： 袁芬，陶琳，徐從富，等. 自適應選擇gossiping概率的多跳網絡數(shù)據廣播[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.
Multi-hop network data broadcast protocol based on adaptive selection gossiping probability
Yuan Fen1，Tao Lin2，Xu Congfu3，Wei Linjing4
1.Department of Computer and Information Technology，Zhejiang Changzheng Vocational & Technical College， Hangzhou 310023，China； 2.Department of Electronical and Information Engineering，Henan Polytechnic Institute，Nanyang 473000，China； 3.College of Computer Science and Technology，Zhejiang University，Hangzhou 310027，China； 4.College of Information Science and Technology，Gansu Agriculture University，Lanzhou 730070，China
Abstract： Mobile Ad Hoc wireless network nodes took up a lot of network resources and the energy cost of the larger broadcast information in the broadcast packet information. To solve these problems, a multi-hop network data broadcast protocol based on adaptive selection gossiping probabilistic is proposed. The protocol defines the gossiping probability based on the number of network nodes and node density distribution of the average neighbor, to reduce the cost of the broadcast information. It adds the ability to select an adaptive gossiping probability, and excludes the nodes will bring node transmission interruption from the candidate neighbor nodes. Simulation results show that compared with gossiping routing protocols, perceived opportunities transmission Ad Hoc routing protocols and lightweight mobile Ad Hoc network active source routing protocols, the network total energy consumption decreases by 32.5%, 14.6% and 2.1%，and can reduce packet loss rate and reduce packet transmission delay well.
Key words : Ad Hoc networks；data broadcast protocol；adaptive selection gossiping probability；energy analysis

0 引言

　　移動Ad Hoc無線網絡是由共享無線介質的移動節(jié)點組成，移動節(jié)點能夠根據需要構建任意的拓撲結構，不需要固定的基礎設施及中央管理系統(tǒng)的加入[1-2]。由于移動節(jié)點隨機分布，兩個無法直接進行通信的節(jié)點還能夠通過其他節(jié)點協(xié)作進行分組轉發(fā)[3-4]，不依賴于現(xiàn)有的網絡通信設施，具有一定的獨立性，適合復雜環(huán)境通信及災難救助等應用[5-6]。文獻[7]提出Ad Hoc網絡中一種鏈路負載均衡的節(jié)能路由協(xié)議，協(xié)議通過考慮網絡中節(jié)點生存時間和節(jié)點間鏈路通信效率兩個方面因素，重新定義和計算鏈路性能,以達到優(yōu)化路由選擇的效果的目的。文獻[8]提出一種基于平均場均衡的Ad Hoc網絡路由協(xié)議，要求每個節(jié)點利用所有其他節(jié)點的信息來分析自己的最優(yōu)策略,而不需要知道每一個局中人的信息,并且在足夠大的局中人數(shù)目情況下性能更加近似馬爾科夫均衡，在節(jié)點密集的無線自組織網絡中路由協(xié)議在包投遞率、時延和歸一化開銷方面獲得了比較好的效果。文獻[9]提出TOAR：傳輸感知的機會Ad Hoc路由協(xié)議，該協(xié)議通過數(shù)學模型求解OR協(xié)議產生重復數(shù)據包的總數(shù)量，采用樹拓撲選擇轉發(fā)節(jié)點的優(yōu)先級次序，盡可能得減少數(shù)據包重傳數(shù)量。文獻[10]提出PSR：一個輕量級的移動Ad Hoc網絡主動源路由協(xié)議，該協(xié)議基于鏈路狀態(tài)信息、距離信息對傳輸路由進行優(yōu)化，使源節(jié)點選擇開銷更小的數(shù)據傳輸鏈路。

1 自適應選擇gossiping概率方法

　　Gossiping路由協(xié)議是對Flooding路由協(xié)議的改進，使用隨機原則，節(jié)點發(fā)送數(shù)據時不再采用廣播形式，而是根據概率隨機轉發(fā)數(shù)據包到鄰居節(jié)點，接著該鄰居節(jié)點再以相同的方式向其鄰近節(jié)點轉發(fā)該數(shù)據包，直到數(shù)據包到達接收終端[11-12]。本文提出的方法旨在減少冗余路由數(shù)據包，減少網絡整體開銷，節(jié)省能源消耗。

　　假設網絡場景為移動節(jié)點隨機分布的自組織網絡，該Ad Hoc無線通信網絡的節(jié)點共享一個無線電信道，節(jié)點可以通過無線信道在傳輸半徑r范圍內互相通信，并且可以通過多跳路徑的方式將信息傳輸給較遠的節(jié)點，除非某一節(jié)點不在其他任何節(jié)點的通信范圍內，這種情況該節(jié)點則無法與相鄰節(jié)點交換信息。由于所有節(jié)點都均勻且獨立地分布于網絡區(qū)域中，在范圍r內一個節(jié)點找到n個鄰居節(jié)點的概率可以用二項概率密度函數(shù)來定義：

　　J~PJYZ080A~G2RJ5FBCJ80O.png

　　其中，V表示網絡節(jié)點的總數(shù)量，S表示網絡總覆蓋面積。

　　由于QQ圖片20161114104348.png，本文采用泊松分布均值QQ圖片20161114104352.png可以將式(1)轉化為：

　　XXH_ZJUA56~3~C{12R16`[I.png

　　一個節(jié)點在其傳輸范圍r內有至少一個相鄰節(jié)點的概率為：

　　QQ圖片20161114104016.png

　　因此，一個節(jié)點在其傳輸范圍內的預期平均鄰居節(jié)點數(shù)量可以表示為：

　　QQ圖片20161114104020.png

　　接下來討論在該gossiping概率下鄰居轉發(fā)節(jié)點的選擇問題。

　　已知一個節(jié)點在其傳輸范圍內的預期鄰居節(jié)點數(shù)量為An，采用傳統(tǒng)的廣播泛洪的方法則會傳輸與路由相關的數(shù)據包至其傳輸范圍內的所有鄰居節(jié)點，能量開銷較大，而gossiping路由則是以隨機概率的形式傳輸數(shù)據包至鄰居節(jié)點，能量開銷小，但傳輸成功率不可靠。而本文采用自適應選擇的gossiping概率方法，則是首先排除掉無下一跳節(jié)點的鄰居節(jié)點，再根據網絡平均鄰居節(jié)點數(shù)與發(fā)送節(jié)點的實際鄰居節(jié)點數(shù)情況，通過自適應的概率條件傳輸數(shù)據包至鄰居節(jié)點。在節(jié)省能量開銷的同時保持傳輸成功率，是本文設計自適應選擇gossiping概率方法的目的。

　　式(4)已知預期平均鄰居節(jié)點數(shù)為An，本文首先定義網絡的自適應gossiping概率為QQ圖片20161114104524.jpg，則：

　　QQ圖片20161114104023.png

　　對于n>An的情況，如果?滋n過低，則說明總節(jié)點數(shù)量過少，總覆蓋面積過大，平均鄰居節(jié)點數(shù)量An過少，此時即使發(fā)送節(jié)點的實際鄰居節(jié)點n較多，但該發(fā)送節(jié)點的鄰居節(jié)點可能過少甚至沒有，此時路由請求信息可能會消失；如果QQ圖片20161114104524.jpg過高，則網絡在發(fā)送路由信息上存在著巨大的開銷。為了避免這種情況，提高任一個發(fā)送節(jié)點i的傳輸可靠性及減少能量開銷。本文假設發(fā)送節(jié)點i的下一跳鄰居節(jié)點集為QQ圖片20161114104720.jpg，且鄰居節(jié)點QQ圖片20161114104622.png，為QQ圖片20161114104524.jpg增加選擇能力，則表達式優(yōu)化為：

　　QQ圖片20161114104027.png

　　對于網絡的自適應選擇gossiping概率QQ圖片20161114105024.png，QQ圖片20161114105027.png表示任一個發(fā)送節(jié)點i的候選鄰居節(jié)點被選擇作為數(shù)據包轉發(fā)節(jié)點的概率，當候選鄰居節(jié)點其自身的下一跳鄰居節(jié)點集為空集時，則該候選鄰居節(jié)點將被徹底排除作為轉發(fā)節(jié)點的可能性。而QQ圖片20161114105031.png，1則是優(yōu)化了QQ圖片20161114104524.jpg的能量開銷問題，當且僅當該節(jié)點的實際鄰居節(jié)點數(shù)量n大于預期平均鄰居節(jié)點數(shù)量，否則自適應選擇的gossiping概率為1。

2 能耗情況分析

　　令V表示節(jié)點總數(shù)，n表示一個節(jié)點在其通信半徑內的平均鄰居節(jié)點數(shù)量，Prece假設為廣播一個數(shù)據包的節(jié)點接收功率，Ptrans表示節(jié)點發(fā)射功率。對于每個節(jié)點發(fā)送的分組總數(shù)和每個節(jié)點接收的平均分組數(shù)量，分別用Ktrans和Krece表示。

　　采用泛洪的廣播數(shù)據方式，當節(jié)點接收到一個數(shù)據包時，它轉發(fā)n個數(shù)據包至其n個鄰居節(jié)點，因此采用泛洪的廣播數(shù)據方式的QQ圖片20161114105237.png。對應的節(jié)點能量總開銷為：

　　QQ圖片20161114104031.png

　　而采用gossiping概率隨機廣播的方式，則節(jié)點接收到上一個節(jié)點發(fā)送的數(shù)據包以及轉發(fā)數(shù)據包到鄰居節(jié)點是以概率性的方式，QQ圖片20161114105317.pngK。對應的節(jié)點能量總開銷為：

　　QQ圖片20161114104037.png

　　而采用自適應選擇的gossiping概率方法進行廣播數(shù)據包，QQ圖片20161114105413.png，假設每個節(jié)點都有鄰居節(jié)點，當n>An，則對應的節(jié)點能量總開銷為：

　　QQ圖片20161114104040.png

　　當QQ圖片20161114105431.png，則對應的節(jié)點能量總開銷為：

　　QQ圖片20161114104043.png

　　則QQ圖片20161114105446.png。

3 實驗仿真及分析

　　在本文實驗的部分，采用的仿真模擬器為NS2，仿真實驗場景為500×500的正方形區(qū)域，網絡中節(jié)點數(shù)量的變化范圍為(200，800)，其中有20個為數(shù)據發(fā)送端源節(jié)點，節(jié)點的通信半徑為100 m，所有節(jié)點都隨機分布于網絡場景中。源節(jié)點每一秒發(fā)送一個數(shù)據包，數(shù)據包大小為512 B，其他仿真參數(shù)如表1所示。

圖像 004.png

　　圖1顯示了在移動節(jié)點數(shù)量變化條件下的網絡節(jié)點總能耗情況，gossiping路由協(xié)議只是采取概率性的鄰居節(jié)點選擇策略，網絡節(jié)點總能耗情況取決于gossiping概率p。p越大，總能耗越大。TOAR算法通過減少數(shù)據包傳輸達到節(jié)省能耗的目的，PSR算法則是通過傳輸鏈路優(yōu)化來節(jié)省發(fā)送數(shù)據包的開銷。本文提出的AS-gossiping算法通過使gossiping概率具有選擇能力從而避免傳輸中斷的情況，減少不必要的能量開銷，同時自適應gossiping概率也減少了在路由信息上的開銷，因此節(jié)能性能更好，相比gossiping路由協(xié)議，TOAR協(xié)議和PSR協(xié)議分別減少了32.5%、14.6%和2.1%的總能耗。

圖像 001.png

　　圖2顯示了在移動節(jié)點數(shù)量增多條件下的數(shù)據包平均丟失率情況，從圖中可以看出，隨著移動節(jié)點數(shù)量的增多，數(shù)據包平均丟失率減小，這是由于每個節(jié)點的平均鄰居節(jié)點數(shù)量增多，gossiping路由協(xié)議可以將同一分組數(shù)據包傳遞給更多的鄰居節(jié)點，數(shù)據包成功傳遞到目的節(jié)點的成功率大大增加。對于TOAR和PSR算法來說，則是可以選擇的下一跳節(jié)點增多，傳輸鏈路的能量效率大大提高。而本文算法數(shù)據包平均丟失率減少的原因與gossiping路由協(xié)議相同，但相比gossiping路由協(xié)議，本文算法還減少了傳輸中斷情況，因此在減少丟包率上表現(xiàn)出更好的性能。

圖像 002.png

　　圖3顯示了在移動節(jié)點數(shù)量增加條件下的數(shù)據包傳輸延遲情況。從圖中的仿真結果來看，gossiping路由協(xié)議的數(shù)據包延遲情況較嚴重，而所有算法的數(shù)據包延遲時間都隨著節(jié)點數(shù)量的增加而增加，這是因為每個節(jié)點的平均鄰居節(jié)點增多，而Ad Hoc網絡采用的是多跳傳輸方式，跳數(shù)的增加伴隨而來的是傳輸時間的增多。由于本文算法的gossiping概率考慮了節(jié)點密度，當鄰居節(jié)點越多，gossiping概率越小，相鄰較近的節(jié)點不一定被選中，因此在跳數(shù)增加上并不明顯。

圖像 003.png

4 結束語

　　本文提出基于對gossiping路由協(xié)議的研究，針對gossiping概率廣播信息開銷較大及傳輸中斷概率較大的情況，提出一種基于自適應選擇gossiping概率的多跳網絡數(shù)據廣播協(xié)議。其中自適應選擇gossiping概率方法能夠對鄰居節(jié)點進行篩選，排除可能帶來中斷鏈路的鄰居節(jié)點，減少傳輸中斷概率，提高能量效率。對候選的鄰居節(jié)點采用自適應gossiping概率進行數(shù)據包廣播，自適應gossiping概率基于發(fā)送節(jié)點實際鄰居節(jié)點數(shù)與網絡節(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網絡中一種鏈路負載均衡的節(jié)能路由協(xié)議[J].計算機技術與發(fā)展，2014(1)：85-88.

　　[8] 張旭，錢志鴻，劉影，等.基于平均場均衡的Ad hoc網絡路由協(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.

　　

　

　　

　　


此內容為AET網站原創(chuàng)，未經授權禁止轉載。