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

姚文強 楊 哲 朱艷琴 李領治

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

?

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

姚文強 楊 哲 朱艷琴 李領治

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

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

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

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

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

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

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

(1)

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

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

2.1 簡單代數模型

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

(2)

N趨于無窮大時,可得

(3)

式(3)的解為

(4)

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

2.2 節點度的影響

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

(5)

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

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

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

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

節點被訪問過2次后舊連接條數為

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

(6)

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

(7)

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

節點被訪問過3次后舊連接數為

(8)

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

(9)

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

節點被訪問過i次后舊連接條數為

(10)

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

(11)

2.3 訪問次數的影響

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

(12)

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

(13)

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

(14)

模型中的階數與節點被訪問次數k有關.

3 實驗結果與分析

根據式(12),在節點數為N的網絡中,若x個消息被轉發后覆蓋了u(x)個節點,則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時,節點被重復訪問2次以上的概率qk(x)(k>2)接近于零.因此,實驗中不考慮k>2的情況，僅利用一階模型(k=1)和二階模型(k=2)來分析消息傳播過程.

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

3.1 一階模型

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

值得注意的是,當d=4,6時, 一階模型理論值大于仿真結果,說明隨著轉發消息數的增加,一階模型仍會高估消息覆蓋的節點數. 這是因為當節點度較小時,圖不連通.在包含2 000個節點的隨機圖網絡中,節點度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時,隨著轉發消息數的增加,一階模型會低估消息覆蓋的節點數.這是因為在轉發消息數較小時,節點被多次訪問的概率較小.然而,當消息數足夠大時,節點被多次訪問的概率也會變大.因此,可用二階模型替換一階模型.二階模型、隨機抽樣模型及仿真實驗得到的消息覆蓋節點數對比見圖2.

(a) d=4

(b) d=6

(c) d=10

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

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

4 結語

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

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—),男,碩士生;楊哲(聯系人),男,博士,副教授,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