基于平均度與平均聚類系數的RWP模型的研究

周　密，　蔡青松，　張迎新

(北京工商大學 計算機與信息工程學院， 北京　100048)

隨機路點(random way point，RWP)[1]模型由于其實現簡單，便于用數學語言描述，被廣泛應用在移動自組織網絡(mobile ad-hoc network，MANET)研究中. 機會網絡作為MANET研究的一個分支，其特點在于機會網絡在大部分時間是非連通的，而傳統的MANET主要考慮網絡連通的情況. 在這種特殊性下，我們需要重新評估RWP模型是否適合作為描述機會網絡的節點移動模型. 本文在前人的研究基礎上繼續對RWP模型進行深入的分析，并從復雜網絡理論中引入平均度以及平均聚類系數兩個重要的概念，通過與實驗數據的比較，分析了RWP模型對機會網絡節點移動模型的仿真效果.

1　平均度與平均聚類系數

1.1　平均度

某個節點i的度Di定義為與節點i所連的節點個數. 節點的度又有兩個延伸概念，最小度與平均度. 一個網絡中度最少的節點的度為網絡的最小度，如果一個網絡中最小度大于等于1則這個網絡是連通的. 在文獻[2]中討論了有關RWP模型最小度的結論，但在機會網絡節點構成的無向圖中可能同時存在多個孤點. 一個n節點無向圖可能是由一個n-1個節點的完全圖和一個孤點構成，也可能是由n個孤點構成，如圖1的(a)和(b). 這兩種情況的最小度都是0，最小度不能適當的描述網絡的連接性.

圖1　兩個最小度為0的無向圖Fig.1　Two undirected graph with minimum degree zero

平均度為所有節點的度的算術平均值：

可以算出圖1(a)的平均度為：

圖1(b)的平均度為：

所以在機會網絡中,使用平均度來表現網絡的連接特性更為科學.

1.2　平均聚類系數

聚類系數是描述網絡節點聚集程度的參數，節點i的聚類系數定義為：節點i的鄰居之間所實際具有的邊數與可能有的邊數的比值. 即，

其中ki為節點i的度，即節點i的鄰居數.Ei為這些鄰居之間實際具有的邊數.

由于單個節點的聚類系數受到該節點的移動路徑的影響很大，所以可以通過計算全部節點的聚類系數并求其均值來觀察整個網絡的節點聚集情況. 網絡的平均聚類系數定義為：

可以通過分析平均聚類系數隨時間的變化來觀察節點的聚集趨勢.

2　RWP模型與實驗數據

2.1　RWP模型的定義

RWP模型是一種理想化的分析模型，所以在RWP模型中有很多的假設條件，使得RWP模型在仿真移動自組織網絡時有一定的偏差，很多文獻中也都指出了RWP模型的節點分布并不均勻[3-4]，但在真實環境下節點的分布往往也不是均勻的，如果RWP模型與真實環境下的這種非均勻性有某種關聯或者相似性，那么使用RWP模型來作為機會網絡的仿真節點移動模型就是合理的，或者說有相當的參考價值. 反之則需要用考慮使用其它的移動模型來仿真機會網絡的節點移動.

下面給出RWP模型的定義：

初始分布函數為finit(x)的n個節點分布在模擬區域Q中，每個節點的運動相互獨立，其中靜止的節點數量占總結點數量的比例用ps表示，并假設節點在目的地的停留時間tp的概率密度函數為fTp(tp)，移動節點的速度范圍為[Vmin,Vmax]. 每個節點的隨機移動過程可以用以i為標號的移動周期構成的集合{Di,Tp,i,Vi}i∈N來表示，每個移動周期中，節點先停留Tp,i，再以速度Vi向Di勻速移動. 其中Di是模擬區域內隨機選定的目的位置；Tp,i為該移動周期中停留的時間，其概率密度函數為fTp(tp)；Vi表示在這個移動周期中節點的移動速度，在[Vmin,Vmax]中選取.

2.2　RWP模型仿真數據的生成

我們在實驗中使用卡內基梅隆大學開發的RWP模型仿真工具setdest[5-6]生成仿真數據. 為了得到比較典型的數據，使用長方形的模擬區域，設定全部節點都是移動節點，停留時間設為常量并規定節點的初始分布為二維均勻分布.

為了形象的說明，下面以一條命令為例說明：

./setdest-v 1 -n 10 -p 20 -M 15 -t
2000 -x 500 -y 800

該命令代表如下的RWP模型場景：在一個500 m×800 m的區域里面均勻分布著10個節點，每個節點在移動周期開始時先停留20 s，然后在仿真區域里隨機選擇一個目的位置，然后在(0,15]之間隨機選定一個速度(單位：m/s)，勻速向目的點移動. 到達目的地以后再開始下一個移動周期，整個運動過程持續2 000 s.

2.3　實驗數據

研究所用的真實實驗數據來源于2006年西班牙巴塞羅納INFOCOM06期間，劍橋大學進行的實驗六[7](Exp6). 項目組分發給與會的學生和研究員便攜的小型設備來采集連接信息，實驗計時從2006年4月23日凌晨開始，到23日下午5點鐘所有設備全部啟動，持續到4月27日. 在整理好的實驗數據中節點標號1～20的為固定節點，21～98為攜帶在與會的學生和研究員身上的便攜設備.

需要說明的是，由于實驗中使用的只是測試連接性的便攜設備，每個設備的開啟時間和掃描周期會有個體差異，在實驗數據中往往會有下面2種情況：

1)節點相遇持續時間為零

在實驗數據中節點A與節點B建立連接時間和連接失效時間相同，這意味著在連續兩次掃描時間內，兩個節點就離開了彼此的通信范圍，很明顯這種情況在實際中無法完成數據的交換，在本文對應的實驗中將其處理為無效的連接數據，不參與計算參數的計算.

2)連接的不對稱性

在實驗數據中同一時刻，節點A有掃描到節點B的記錄，但B沒有相應的掃描到A的記錄，考慮到掃描的時間不是完全同步的，而且計算連接性的時間抽樣點也是離散的，研究假設在這種情況下A和B是可以進行通信的. 在計算某時刻平均度和聚類系數時只要兩個節點其中之一可以連接到另外一個節點就按雙向連接計算.

3　關鍵參數的對比分析

3.1　節點的平均相遇持續時間

相遇持續時間是指兩個節點進入彼此的通信范圍到離開對方的通信范圍之間的時間，通過兩組實驗來觀察RWP模型中節點平均相遇持續時間的規律.

第一組實驗，在長寬都為500 m的模擬區域內進行100 000 s的模擬，節點最大移動速度為50 m/s,停留時間從0 s變化到1 000 s，結果如圖2.

圖2　平均相遇持續時間與停留時間的關系Fig.2　Average contact duration and pause time

平均相遇持續時間與擬合直線符合度很高，說明相遇持續時間與停留時間成線性關系.

從RWP模型的定義可以知道節點的一個運動周期分為兩個階段，一個是停留階段，一個是移動階段. 當最大速度一定時，停留時間越長則停留階段在運動周期中所占的時間比例也就越高，節點的整體移動性下降，因此導致平均相遇持續時間也呈線性增長，實驗的結果與理論是相符的.

第二組實驗，固定停留時間為50 s，再讓節點最大移動速度從1 m/s變化到100 m/s，可以看到停留持續時間急速下滑后趨于穩定，在對數坐標系下呈一條直線，可以被冪率分布曲線很好的擬合，如圖3.

圖3　平均相遇持續時間與最大運動速度的關系Fig.3　Average contact duration and max speed

圖3給出的直觀含義是當節點移動性較弱，停留階段占移動周期的比例很高時，節點移動速度對網絡的拓撲的穩定性影響很大；而當停留階段占移動周期的比例變小以后，節點的移動速度對網絡拓撲的影響力也急劇變小.

而實際上這種現象證明了RWP模型節點的聚集效應的存在[8]，由于RWP模型中節點在每個移動周期選擇目的點的方式是在仿真區域內隨機選取，所以必然導致節點有像仿真區域中間移動的趨勢. 對于機會網絡來說，比如人類的社會活動當中，人們也會有向某個中心聚集的趨勢：上課時學生會向教室聚集，超市購物時消費者會向收銀臺聚集等，所以存在使用RWP模型仿真機會網絡具有合理性的可能.

3.2　節點的相遇時間間隔

相遇時間間隔表示兩個節點在兩次相遇之間經歷的時間，在文獻[9]中，通過實驗數據得到了在機會網絡中節點相遇時間間隔為冪率分布的結論.

通過實驗來觀察RWP模型中相遇時間間隔的分布情況，如圖4.

可以在圖4中看出在對數坐標系下，相遇時間間隔的分布呈一條直線，這說明了RWP模型的相遇間隔時間與機會網絡相似，也服從冪率分布.

圖4　RWP模型中相遇時間間隔的分布Fig.4　Distribution of inter-meeting time in RWP model

3.3　網絡平均度和平均聚類系數

雖然在前面的分析中，看到RWP模型與機會網絡單個節點隨時間變化的參數十分相似，但所有節點構成的網絡拓撲的規律仍有待考察，下面使用平均度和平均聚類系數來分析仿真數據和實驗數據的聚集特性.

setdest仿真條件為：1 000 m×1 000 m的區域里均勻分布的50個節點，停留時間為0 s，最大速度為10 m/s，仿真時間為1 000 s. 與之對比的實際數據為Exp6. 將仿真數據和實驗數據整理成同樣的數據格式來觀察平均度和聚類系數的關系.

觀察圖5(a)和圖5(c)可以很清晰地發現在仿真開始時RWP模型的變化幅度很大，這是由于研究簡單地假定RWP模型的初始分布為均勻分布，而實際上在xm×ym的矩形模擬區域中，RWP模型穩定的分布函數可以近似為：

這種現象稱為RWP模型的初始效應，為了和實驗數據做對比，觀察RWP模型在實驗時間到達250 s基本穩定以后的數據. 對于用來對比的Exp6的數據，研究認為60 000 s以后的實驗數據為有效值，因為60 000 s以前的波動是由于那個時段在夜里，作為節點的實驗人員的活動與RWP的仿真參數不符合.

通過對比圖5(a)、(b)、(c)和(d)可以看出，RWP仿真數據的平均度和實驗數據平均度的浮動區間大概在4到6之間；RWP模型的聚類系數的變化區間為0.57到0.72，而此時圖5(d)實驗數據中聚類系數的變化范圍在0.11到0.28之間.

圖5　RWP模型與Exp6數據的參數對比Fig.5　Comparison between RWP model and Exp6 Data

平均度是體現機會網絡連接特性的參數，當兩個機會網絡的平均度相近時，說明兩個網絡的連接性也應該是接近的，RWP模型與Exp6數據在平均度相近的情況下，RWP模型的平均聚類系數卻遠遠高于Exp6，說明RWP模型的連通性要比機會網絡理想得多，而機會網絡中會存在更多更小的子網和孤點，正是由于小子網和孤點的大量存在導致了機會網絡的聚類系數要低于RWP模型的仿真結果. 如果使用RWP模型來仿真機會網絡的節點移動，會對網絡的連通性有過高的估計，在這樣條件下滿足要求的路由協議顯然無法滿足實際的需要.

4　結　論

本文對比分析了RWP模型和Exp6數據中反應移動模型特性的參數，分析數據表明RWP模型中節點間相遇持續時間與相遇時間間隔的分布情況與機會網絡類似，但從整個網絡的節點聚集情況來看RWP模型的仿真結果過于理想化，因此不適合作為描述機會網絡的仿真移動模型.

盡管RWP模型的聚類特性與機會網絡不同，但是作為經典的移動模型RWP在MANET研究中的重要意義是不能否認的. 機會網絡中節點移動的規律十分復雜，很難用數學語言來描述，但可以以對RWP模型的研究為基礎，找到更適合描述機會網絡的移動模型.

本文得到的結論對于機會網絡和MANET的研究都有一定的參考價值，找到適合描述機會網絡的移動模型還需要進行其它的對比實驗，真正實現可以投入應用的MANET還需要通過長期的探索和研究.