Ad hoc網絡消息傳播過程的高階描述模型

姚文強 楊 哲 朱艷琴 李領治

(蘇州大學計算機科學與技術學院,蘇州215006)(蘇州大學江蘇省計算機信息處理技術重點實驗室,蘇州215006)

?

Ad hoc網絡消息傳播過程的高階描述模型

姚文強 楊 哲 朱艷琴 李領治

(蘇州大學計算機科學與技術學院,蘇州215006)(蘇州大學江蘇省計算機信息處理技術重點實驗室,蘇州215006)

為避免采用隨機抽樣模型對Ad hoc網絡消息傳播過程進行定量分析時存在的高估消息覆蓋節(jié)點數(shù)的問題,對現(xiàn)有模型進行修正，提出了一種高階描述模型.該模型在轉發(fā)消息時考慮了會對下一次消息轉發(fā)到達新節(jié)點的概率產生影響的2個參數(shù):節(jié)點被訪問次數(shù)和節(jié)點度.節(jié)點被訪問的次數(shù)越多，模型的階數(shù)越高.在包含2 000個節(jié)點的隨機圖網絡拓撲上的仿真試驗結果表明，當消息覆蓋的節(jié)點數(shù)超過1 800時，無論拓撲是否連通，一階模型和二階模型對Ad hoc網絡消息傳播過程的擬合度均優(yōu)于隨機抽樣模型.當網絡拓撲不連通時,一階模型和二階模型仍會高估消息覆蓋的節(jié)點數(shù);相反,當網絡拓撲連通時,兩者對仿真結果的擬合度較好，最終誤差分別為-7%和-1%.

Ad hoc網絡;消息傳播過程;節(jié)點覆蓋;高階模型

Ad hoc網絡是一種自治、多跳系統(tǒng),每個節(jié)點在發(fā)送消息的同時,也轉發(fā)其他節(jié)點的消息,以實現(xiàn)資源共享和協(xié)作.在Ad hoc網絡中進行節(jié)點或資源的搜索與定位時,主要通過網絡內傳播查詢消息來完成.節(jié)點覆蓋問題是指從整體性能的角度,轉發(fā)盡可能少的消息來覆蓋盡可能多的節(jié)點[1].由于Ad hoc節(jié)點的加入和離開是動態(tài)的,因此網絡拓撲是動態(tài)隨機的[2].研究Ad hoc網絡消息傳播過程時,一般采用隨機游走法[3-5]、洪泛法[6]或者其他變異方法[7-12].其中,洪泛法的響應速度最快,但傳播開銷最大;隨機游走法雖然響應速度慢,但在消息覆蓋的節(jié)點數(shù)和傳播開銷等方面性能較好,是目前主要運用的方法[13].其中,消息覆蓋的節(jié)點數(shù)(即網絡中消息經過的節(jié)點數(shù)量)是一個關鍵問題.當網絡中節(jié)點較多且消息經過的節(jié)點數(shù)較少時,消息傳播過程可以用隨機抽樣模型描述;但隨著消息在網絡節(jié)點間的不斷擴散,隨機抽樣模型會高估消息覆蓋的節(jié)點數(shù).

本文通過引入節(jié)點被訪問次數(shù)和節(jié)點度2個參數(shù),對隨機抽樣模型進行修正.著重分析了兩者對下一次消息轉發(fā)到達新節(jié)點的概率所產生的影響,并推導出相應的計算方法.

1 消息傳播過程的隨機抽樣模型

φ(z)=M(1-e-z/M)

(1)

但消息在Ad hoc網絡中的傳播過程并不是一個完全獨立隨機過程[13].消息到達某個節(jié)點后,下一跳恰好選擇一條新的連接從而到達一個新節(jié)點的概率,不僅與當前網絡中新節(jié)點的個數(shù)有關,也與當前節(jié)點度及被消息訪問的次數(shù)有關;而隨機抽樣模型并不考慮這2個因素.因此,在估計某一時刻Ad hoc網絡中消息已覆蓋的節(jié)點數(shù)時,會出現(xiàn)估計值過高的問題.

2 消息傳播過程的高階描述模型

2.1 簡單代數(shù)模型

Ad hoc網絡拓撲可用隨機圖G(N,P)表示,共有N個節(jié)點,任意2個節(jié)點間存在連接的概率為P(0

(2)

N趨于無窮大時,可得

(3)

式(3)的解為

(4)

式(4)所示的簡單代數(shù)模型在計算每次消息轉發(fā)到達新節(jié)點的概率時,都假設其等于未訪問節(jié)點數(shù)和總節(jié)點數(shù)之比,即[N-u(x)]/N.這種假設只有在消息第1次訪問該節(jié)點時才成立.當節(jié)點已經被訪問后,這一概率會下降,下降幅度與節(jié)點度有關.節(jié)點度越大,消息仍能以較高的概率到達其他新節(jié)點.在極端情況下,如果節(jié)點被多次訪問,所有連接均被遍歷后,當消息再次訪問該節(jié)點時,則不可能經由一條新連接到達其他新的節(jié)點.因此,需要對式(4)所示的簡單代數(shù)模型進行修正,引入節(jié)點度和節(jié)點被訪問次數(shù)2個參數(shù),重新計算每次消息轉發(fā)到達新節(jié)點的概率.

2.2 節(jié)點度的影響

在式(2)中,當前消息覆蓋的節(jié)點數(shù)為u(x),令p(x)為節(jié)點通過一條新連接將消息轉發(fā)給一個新的鄰居節(jié)點的概率,則消息轉發(fā)后覆蓋的節(jié)點數(shù)u(x+1)為

(5)

下面以節(jié)點被訪問的次數(shù)k作為分支條件,討論節(jié)點被訪問k次后仍存在新連接的概率pk.

1) 當k=0時,消息首次訪問該節(jié)點,節(jié)點的所有連接都是新連接.此時節(jié)點存在新連接的概率為p0=1.

2) 當k=1時,節(jié)點的舊連接數(shù)L1=2,即一條進一條出,則消息經過新連接被轉發(fā)的概率為p1=(d-2)/d,其中d為節(jié)點度.

3) 當k=2時,節(jié)點存在多條舊連接的可能性變得復雜.令wk(i)表示節(jié)點被訪問k次后擁有i條舊連接的概率,則此時節(jié)點存在2,3,4條舊連接的概率w2(2),w2(3),w2(4)分別為

節(jié)點被訪問過2次后舊連接條數(shù)為

L2=2w2(2)+3w2(3)+4w2(4)

(6)

節(jié)點被訪問過2次后,下一次消息轉發(fā)仍能經過一條新連接到達一個新節(jié)點的概率為

(7)

4) 當k=3時,在節(jié)點舊連接數(shù)為L2的條件下,經過下一輪轉發(fā),變成L2,L2+1,L2+2條舊連接的概率分別為

節(jié)點被訪問過3次后舊連接數(shù)為

(8)

同理,節(jié)點被訪問過3次后,下一次消息轉發(fā)仍能經過一條新連接到達一個新節(jié)點的概率為

(9)

5) 以此類推,當節(jié)點被訪問過i(i>3)次后,舊連接數(shù)為Li-1,經過下一輪轉發(fā)后變成Li-1,Li-1+1和Li-1+2條舊連接的概率分別為

節(jié)點被訪問過i次后舊連接條數(shù)為

(10)

節(jié)點被訪問過i次后,下一次消息轉發(fā)仍能經過一條新連接到達一個新節(jié)點的概率為

(11)

2.3 訪問次數(shù)的影響

式(5)中的p(x)是一個關于x的隨機函數(shù),取決于當前節(jié)點已經被訪問過k次的概率.假設x個消息被轉發(fā)后覆蓋了u個節(jié)點,則任一節(jié)點被訪問k次的概率為

(12)

p(x)即可表示為節(jié)點被訪問次數(shù)k與節(jié)點存在新連接的概率的加權平均,即

(13)

將式(13)代入式(5),得到如下的高階描述模型:

(14)

模型中的階數(shù)與節(jié)點被訪問次數(shù)k有關.

3 實驗結果與分析

根據(jù)式(12),在節(jié)點數(shù)為N的網絡中,若x個消息被轉發(fā)后覆蓋了u(x)個節(jié)點,則qk(x)會隨著k的增加而迅速減小.例如,當N=2 000,u=1 000,x=1 386時,對于k=0,1,2,3,4分別有q0(x)=0.499 9,q1(x)=0.346 6,q2(x)=0.120 1,q3(x)=0.027 7,q4(x)=0.004 8.可見,當x?N時,節(jié)點被重復訪問2次以上的概率qk(x)(k>2)接近于零.因此,實驗中不考慮k>2的情況，僅利用一階模型(k=1)和二階模型(k=2)來分析消息傳播過程.

基于NS-2 V2.29仿真平臺,模擬了包含2 000個節(jié)點的網絡,網絡拓撲服從隨機圖模型[16].本文僅針對消息傳播過程進行研究,因此不考慮消息傳輸?shù)臅r延和丟包等情況,所有消息數(shù)據(jù)包大小為1 B.實驗開始時,隨機選擇1個節(jié)點作為消息源,向其鄰居節(jié)點擴散消息.所有收到消息的節(jié)點在1個時鐘周期內僅允許轉發(fā)1次該消息.在每個時鐘周期結束后,統(tǒng)計當前消息覆蓋的節(jié)點數(shù).待節(jié)點轉發(fā)消息的次數(shù)累計達到1×104時,實驗結束;以10次實驗的平均值作為仿真結果.

3.1 一階模型

當d=4,6,10時, 一階模型、隨機抽樣模型及仿真實驗得到的消息覆蓋節(jié)點數(shù)對比見圖1.由圖可知, 一階模型理論值曲線更接近仿真結果曲線,說明相比隨機抽樣模型,一階模型對消息傳播過程的擬合度更高.

值得注意的是,當d=4,6時, 一階模型理論值大于仿真結果,說明隨著轉發(fā)消息數(shù)的增加,一階模型仍會高估消息覆蓋的節(jié)點數(shù). 這是因為當節(jié)點度較小時,圖不連通.在包含2 000個節(jié)點的隨機圖網絡中,節(jié)點度d=P(N-1),當d=4時,P=0.002,當d=6時，p=0.003.PN

(a) d=4

(b) d=6

(c) d=10

3.2 二階模型

由圖1(c)可知,當d=10時,隨著轉發(fā)消息數(shù)的增加,一階模型會低估消息覆蓋的節(jié)點數(shù).這是因為在轉發(fā)消息數(shù)較小時,節(jié)點被多次訪問的概率較小.然而,當消息數(shù)足夠大時,節(jié)點被多次訪問的概率也會變大.因此,可用二階模型替換一階模型.二階模型、隨機抽樣模型及仿真實驗得到的消息覆蓋節(jié)點數(shù)對比見圖2.

(a) d=4

(b) d=6

(c) d=10

當d=4,6時,二階模型理論值仍大于仿真結果,這同樣是由于網絡拓撲的連通性問題引起的.但當d=10時,由于網絡是連通的, 二階模型對仿真結果的擬合程度較一階模型好,且隨著網絡中轉發(fā)消息數(shù)的增加,誤差會逐漸減小.當消息轉發(fā)數(shù)小于3×103時, 二階模型理論值與仿真結果的平均擬合誤差為12%;當消息轉發(fā)數(shù)達到5×103時,擬合誤差為-0.1%;當消息轉發(fā)數(shù)達到1×104時,實驗結束,二階模型的消息覆蓋節(jié)點數(shù)為1 807, 仿真結果為1 828, 擬合誤差為-1%.

綜上可知,當消息覆蓋的節(jié)點數(shù)超過1 800時,無論拓撲是否連通,一階模型和二階模型對Ad hoc網絡消息傳播過程的擬合度均優(yōu)于隨機抽樣模型.當網絡拓撲不連通時,一階模型和二階模型仍會高估消息覆蓋的節(jié)點數(shù);當網絡拓撲連通時,兩者對仿真結果的擬合度較好,最終誤差分別為-7%和-1%.

4 結語

在Ad-hoc等協(xié)作通信系統(tǒng)中,消息傳播的目的是通過盡可能少的消息來覆蓋盡可能多的節(jié)點.隨著轉發(fā)消息數(shù)的增加,隨機抽樣模型會高估消息覆蓋的節(jié)點數(shù).本文提出了一種高階描述模型.該模型在轉發(fā)消息時,考慮了節(jié)點被訪問次數(shù)和節(jié)點度對下一次消息到達新節(jié)點的概率所產生的影響及其程度.通過仿真實驗,驗證了高階模型的有效性.由于未考慮網絡拓撲的影響,所得結論僅是在隨機圖網絡拓撲上得出的.而在實際應用中,一般網絡拓撲更接近小世界網絡或冪律網絡.這種網絡拓撲上消息傳播過程的定量分析是今后研究的重點.

References)

[1]Sun Y, Zhang S K, Xu H L, et al. Cooperative communications for wireless ad hoc and sensor networks [J].InternationalJournalofDistributedSensorNetworks, 2013,2013:161268-1-161268-2.

[2]Zhang S K, Fan J X, Jia J C, et al. An efficient clustering algorithm in wireless sensor networks using cooperative communication [J].InternationalJournalofDistributedSensorNetworks, 2012, 2012: 274576-1-274576-11.

[3]Dolev S, Schiller E, Welch J. Random walk for self-stabilizing group communication in ad hoc networks [J].IEEETransactionsonMobileComputing, 2006, 5(7): 893-905.

[4]Bar-Yossef Z, Friedman R, Kliot G. RaWMS-random walk based lightweight membership service for wireless ad hoc networks [J].ACMTransactionsonComputerSystems, 2008, 26(2):5-1-5-66.

[5]Avin C, Krishnamachari B. The power of choice in random walks: an empirical study [J].ComputerNetworks, 2008, 52(1): 44-60.

[6]Chang N B, Liu M. Optimal controlled flooding search in large wireless networks [C]//Proceedingsof3rdInternationalSymposiumonModelingandOptimizationinMobile,AdHoc,andWirelessNetworks. Trentino, Italy, 2005: 229-237.

[7]Jiang S, Guo L, Zhang X D, et al. Lightflood: minimizing redundant messages and maximizing scope of peer-to-peer search [J].IEEETransactionsonParallelandDistributedSystems, 2008, 19(5): 601-614.

[8]Els?sser R, Sauerwald T. Tight bounds for the cover time of multiple random walks [J].TheoreticalComputerScience, 2011, 412(24): 2623-2641.

[9]Beraldi R. Biased random walks in uniform wireless networks [J].IEEETransactionsonMobileComputing, 2009, 8(4): 500-513.

[10]Zuniga M, Avin C, Krishnamachari B. Using heterogeneity to enhance random walk-based queries [J].JournalofSignalProcessingSystems, 2009, 57(3): 401-414.

[11]Bisnik N, Abouzeid A A. Optimizing random walk search algorithms in P2P networks [J].ComputerNetworks, 2007, 51(6): 1499-1514.

[12]Rodero-Merino L, Anta A F, López L, et al. Performance of random walks in one-hop replication networks [J].ComputerNetworks, 2010, 54(5): 781-796.

[13]Kang C. Survey of search and optimization of P2P networks [J].Peer-to-PeerNetworkingandApplications, 2011, 4(3): 211-218.

[14]Xie J, Lui K S. Modeling random walk search algorithms in unstructured P2P networks with social information [C]//Proceedingsof2009IEEEInternationalConferenceonCommunications. Dresden, Germany, 2009: 1-5.

[15]López Millán V M, Cholvi V, López L, et al. A model of self-avoiding random walks for searching complex networks [J].Networks, 2012, 60(2): 71-85.

[16]Erd?s P, Rényi A. On the evolution of random graphs [J].PublicationoftheMathematicalInstituteoftheHungarianAcademySciences, 1960, 5: 17-61.

High-order description model of message propagation process in Ad hoc network

Yao Wenqiang Yang Zhe Zhu Yanqin Li Lingzhi

(School of Computer Science and Technology, Soochow University, Suzhou 215006, China) (Provincial Key Laboratory for Computer Information Processing Technology, Soochow University, Suzhou 215006, China)

To avoid the overestimation problem of the number of nodes covered during the quantitative analysis of message propagation process in Ad hoc network by using the random sampling model, a high-order description model is proposed by modification. In the proposed model, when the message is transmitted, the visit times and the degrees of nodes which influence the probability of the next messages transmitted to new nodes are considered. The more the visit times, the higher the order of the description model. The simulation results on a random graph topology network with 2 000 nodes show that when the number of nodes covered is more than 1 800, the fitting abilities of both the 1-order model and the 2-order model for the message propagation process in Ad hoc network are better than that of the random sampling model whether the network topology is connected or not. When the network topology is disconnected, both the 1-order model and the 2-order model still overestimate the number nodes covered; on the contrary, when the network topology is connected, the fitting degrees of both the 1-order model and the 2-order model for the simulation results are satisfactory, and the final fitting errors are -7% and -1%, respectively.

Ad hoc network; message propagation process; node coverage; high-order model

10.3969/j.issn.1001-0505.2015.03.003

2014-11-13. 作者簡介: 姚文強(1992—),男,碩士生;楊哲(聯(lián)系人),男,博士,副教授,yangzhe@suda.edu.cn.

國家自然科學基金資助項目(61373164)、江蘇省產學研前瞻性研究計劃資助項目(BY2013030-06)、蘇州市科技計劃資助項目(SYG201238, SZS0805).

姚文強,楊哲,朱艷琴，等.Ad hoc網絡消息傳播過程的高階描述模型[J].東南大學學報:自然科學版,2015,45(3):428-432.

10.3969/j.issn.1001-0505.2015.03.003

TP393

A

1001-0505(2015)03-0428-05