周　密，　蔡青松，　張迎新

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

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

1　平均度與平均聚類系數(shù)

1.1　平均度

某個節(jié)點(diǎn)i的度Di定義為與節(jié)點(diǎn)i所連的節(jié)點(diǎn)個數(shù). 節(jié)點(diǎn)的度又有兩個延伸概念，最小度與平均度. 一個網(wǎng)絡(luò)中度最少的節(jié)點(diǎn)的度為網(wǎng)絡(luò)的最小度，如果一個網(wǎng)絡(luò)中最小度大于等于1則這個網(wǎng)絡(luò)是連通的. 在文獻(xiàn)[2]中討論了有關(guān)RWP模型最小度的結(jié)論，但在機(jī)會網(wǎng)絡(luò)節(jié)點(diǎn)構(gòu)成的無向圖中可能同時存在多個孤點(diǎn). 一個n節(jié)點(diǎn)無向圖可能是由一個n-1個節(jié)點(diǎn)的完全圖和一個孤點(diǎn)構(gòu)成，也可能是由n個孤點(diǎn)構(gòu)成，如圖1的(a)和(b). 這兩種情況的最小度都是0，最小度不能適當(dāng)?shù)拿枋鼍W(wǎng)絡(luò)的連接性.

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

平均度為所有節(jié)點(diǎn)的度的算術(shù)平均值：

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

圖1(b)的平均度為：

所以在機(jī)會網(wǎng)絡(luò)中,使用平均度來表現(xiàn)網(wǎng)絡(luò)的連接特性更為科學(xué).

1.2　平均聚類系數(shù)

聚類系數(shù)是描述網(wǎng)絡(luò)節(jié)點(diǎn)聚集程度的參數(shù)，節(jié)點(diǎn)i的聚類系數(shù)定義為：節(jié)點(diǎn)i的鄰居之間所實(shí)際具有的邊數(shù)與可能有的邊數(shù)的比值. 即，

其中ki為節(jié)點(diǎn)i的度，即節(jié)點(diǎn)i的鄰居數(shù).Ei為這些鄰居之間實(shí)際具有的邊數(shù).

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

可以通過分析平均聚類系數(shù)隨時間的變化來觀察節(jié)點(diǎn)的聚集趨勢.

2　RWP模型與實(shí)驗數(shù)據(jù)

2.1　RWP模型的定義

RWP模型是一種理想化的分析模型，所以在RWP模型中有很多的假設(shè)條件，使得RWP模型在仿真移動自組織網(wǎng)絡(luò)時有一定的偏差，很多文獻(xiàn)中也都指出了RWP模型的節(jié)點(diǎn)分布并不均勻[3-4]，但在真實(shí)環(huán)境下節(jié)點(diǎn)的分布往往也不是均勻的，如果RWP模型與真實(shí)環(huán)境下的這種非均勻性有某種關(guān)聯(lián)或者相似性，那么使用RWP模型來作為機(jī)會網(wǎng)絡(luò)的仿真節(jié)點(diǎn)移動模型就是合理的，或者說有相當(dāng)?shù)膮⒖純r值. 反之則需要用考慮使用其它的移動模型來仿真機(jī)會網(wǎng)絡(luò)的節(jié)點(diǎn)移動.

下面給出RWP模型的定義：

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

2.2　RWP模型仿真數(shù)據(jù)的生成

我們在實(shí)驗中使用卡內(nèi)基梅隆大學(xué)開發(fā)的RWP模型仿真工具setdest[5-6]生成仿真數(shù)據(jù). 為了得到比較典型的數(shù)據(jù)，使用長方形的模擬區(qū)域，設(shè)定全部節(jié)點(diǎn)都是移動節(jié)點(diǎn)，停留時間設(shè)為常量并規(guī)定節(jié)點(diǎn)的初始分布為二維均勻分布.

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

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

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

2.3　實(shí)驗數(shù)據(jù)

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

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

1)節(jié)點(diǎn)相遇持續(xù)時間為零

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

2)連接的不對稱性

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

3　關(guān)鍵參數(shù)的對比分析

3.1　節(jié)點(diǎn)的平均相遇持續(xù)時間

相遇持續(xù)時間是指兩個節(jié)點(diǎn)進(jìn)入彼此的通信范圍到離開對方的通信范圍之間的時間，通過兩組實(shí)驗來觀察RWP模型中節(jié)點(diǎn)平均相遇持續(xù)時間的規(guī)律.

第一組實(shí)驗，在長寬都為500 m的模擬區(qū)域內(nèi)進(jìn)行100 000 s的模擬，節(jié)點(diǎn)最大移動速度為50 m/s,停留時間從0 s變化到1 000 s，結(jié)果如圖2.

圖2　平均相遇持續(xù)時間與停留時間的關(guān)系Fig.2　Average contact duration and pause time

平均相遇持續(xù)時間與擬合直線符合度很高，說明相遇持續(xù)時間與停留時間成線性關(guān)系.

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

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

圖3　平均相遇持續(xù)時間與最大運(yùn)動速度的關(guān)系Fig.3　Average contact duration and max speed

圖3給出的直觀含義是當(dāng)節(jié)點(diǎn)移動性較弱，停留階段占移動周期的比例很高時，節(jié)點(diǎn)移動速度對網(wǎng)絡(luò)的拓?fù)涞姆€(wěn)定性影響很大；而當(dāng)停留階段占移動周期的比例變小以后，節(jié)點(diǎn)的移動速度對網(wǎng)絡(luò)拓?fù)涞挠绊懥σ布眲∽冃?

而實(shí)際上這種現(xiàn)象證明了RWP模型節(jié)點(diǎn)的聚集效應(yīng)的存在[8]，由于RWP模型中節(jié)點(diǎn)在每個移動周期選擇目的點(diǎn)的方式是在仿真區(qū)域內(nèi)隨機(jī)選取，所以必然導(dǎo)致節(jié)點(diǎn)有像仿真區(qū)域中間移動的趨勢. 對于機(jī)會網(wǎng)絡(luò)來說，比如人類的社會活動當(dāng)中，人們也會有向某個中心聚集的趨勢：上課時學(xué)生會向教室聚集，超市購物時消費(fèi)者會向收銀臺聚集等，所以存在使用RWP模型仿真機(jī)會網(wǎng)絡(luò)具有合理性的可能.

3.2　節(jié)點(diǎn)的相遇時間間隔

相遇時間間隔表示兩個節(jié)點(diǎn)在兩次相遇之間經(jīng)歷的時間，在文獻(xiàn)[9]中，通過實(shí)驗數(shù)據(jù)得到了在機(jī)會網(wǎng)絡(luò)中節(jié)點(diǎn)相遇時間間隔為冪率分布的結(jié)論.

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

可以在圖4中看出在對數(shù)坐標(biāo)系下，相遇時間間隔的分布呈一條直線，這說明了RWP模型的相遇間隔時間與機(jī)會網(wǎng)絡(luò)相似，也服從冪率分布.

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

3.3　網(wǎng)絡(luò)平均度和平均聚類系數(shù)

雖然在前面的分析中，看到RWP模型與機(jī)會網(wǎng)絡(luò)單個節(jié)點(diǎn)隨時間變化的參數(shù)十分相似，但所有節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)拓?fù)涞囊?guī)律仍有待考察，下面使用平均度和平均聚類系數(shù)來分析仿真數(shù)據(jù)和實(shí)驗數(shù)據(jù)的聚集特性.

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

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

這種現(xiàn)象稱為RWP模型的初始效應(yīng)，為了和實(shí)驗數(shù)據(jù)做對比，觀察RWP模型在實(shí)驗時間到達(dá)250 s基本穩(wěn)定以后的數(shù)據(jù). 對于用來對比的Exp6的數(shù)據(jù)，研究認(rèn)為60 000 s以后的實(shí)驗數(shù)據(jù)為有效值，因為60 000 s以前的波動是由于那個時段在夜里，作為節(jié)點(diǎn)的實(shí)驗人員的活動與RWP的仿真參數(shù)不符合.

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

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

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

4　結(jié)　論

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

盡管RWP模型的聚類特性與機(jī)會網(wǎng)絡(luò)不同，但是作為經(jīng)典的移動模型RWP在MANET研究中的重要意義是不能否認(rèn)的. 機(jī)會網(wǎng)絡(luò)中節(jié)點(diǎn)移動的規(guī)律十分復(fù)雜，很難用數(shù)學(xué)語言來描述，但可以以對RWP模型的研究為基礎(chǔ)，找到更適合描述機(jī)會網(wǎng)絡(luò)的移動模型.

本文得到的結(jié)論對于機(jī)會網(wǎng)絡(luò)和MANET的研究都有一定的參考價值，找到適合描述機(jī)會網(wǎng)絡(luò)的移動模型還需要進(jìn)行其它的對比實(shí)驗，真正實(shí)現(xiàn)可以投入應(yīng)用的MANET還需要通過長期的探索和研究.