姚文強 楊 哲 朱艷琴 李領(lǐng)治

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

?

Ad hoc網(wǎng)絡消息傳播過程的高階描述模型

姚文強 楊 哲 朱艷琴 李領(lǐng)治

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

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

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

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

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

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

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

(1)

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

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

2.1 簡單代數(shù)模型

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

(2)

N趨于無窮大時,可得

(3)

式(3)的解為

(4)

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

2.2 節(jié)點度的影響

在式(2)中,當前消息覆蓋的節(jié)點數(shù)為u(x),令p(x)為節(jié)點通過一條新連接將消息轉(zhuǎn)發(fā)給一個新的鄰居節(jié)點的概率,則消息轉(zhuǎn)發(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,即一條進一條出,則消息經(jīng)過新連接被轉(zhuǎn)發(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次后,下一次消息轉(zhuǎn)發(fā)仍能經(jīng)過一條新連接到達一個新節(jié)點的概率為

(7)

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

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

(8)

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

(9)

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

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

(10)

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

(11)

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

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

(12)

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

(13)

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

(14)

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

3 實驗結(jié)果與分析

根據(jù)式(12),在節(jié)點數(shù)為N的網(wǎng)絡中,若x個消息被轉(zhuǎn)發(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é)點的網(wǎng)絡,網(wǎng)絡拓撲服從隨機圖模型[16].本文僅針對消息傳播過程進行研究,因此不考慮消息傳輸?shù)臅r延和丟包等情況,所有消息數(shù)據(jù)包大小為1 B.實驗開始時,隨機選擇1個節(jié)點作為消息源,向其鄰居節(jié)點擴散消息.所有收到消息的節(jié)點在1個時鐘周期內(nèi)僅允許轉(zhuǎn)發(fā)1次該消息.在每個時鐘周期結(jié)束后,統(tǒng)計當前消息覆蓋的節(jié)點數(shù).待節(jié)點轉(zhuǎn)發(fā)消息的次數(shù)累計達到1×104時,實驗結(jié)束;以10次實驗的平均值作為仿真結(jié)果.

3.1 一階模型

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

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

(a) d=4

(b) d=6

(c) d=10

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

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

4 結(jié)語

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

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)、江蘇省產(chǎn)學研前瞻性研究計劃資助項目(BY2013030-06)、蘇州市科技計劃資助項目(SYG201238, SZS0805).

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

10.3969/j.issn.1001-0505.2015.03.003

TP393

A

1001-0505(2015)03-0428-05