錢(qián)靜豐+楊琦

摘 要： 在影響無(wú)線網(wǎng)絡(luò)同步的因素中，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)逐漸引起人們的關(guān)注。通過(guò)研究RGG模型中網(wǎng)絡(luò)聚類(lèi)系數(shù)和網(wǎng)絡(luò)次大特征值之間的關(guān)系，來(lái)探索聚類(lèi)系數(shù)對(duì)網(wǎng)絡(luò)收斂性能的影響程度，并希望從有邊界效應(yīng)和無(wú)邊界效應(yīng)兩種情況入手對(duì)其進(jìn)行研究。通過(guò)仿真實(shí)驗(yàn)發(fā)現(xiàn)在無(wú)邊界情況下的聚類(lèi)系數(shù)是一個(gè)常數(shù)，與其他因素?zé)o關(guān)，有邊界情況下其值與環(huán)境參數(shù)相關(guān)。從理論上推導(dǎo)了無(wú)邊界聚類(lèi)系數(shù)的理論值，并給出了有邊界情況下的推導(dǎo)思路。

關(guān)鍵詞： Ad Hoc； 網(wǎng)絡(luò)同步； 拓?fù)浣Y(jié)構(gòu)； 聚類(lèi)系數(shù)

中圖分類(lèi)號(hào)： TN92?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2014）07?0005?04

Research on clustering coefficient in RGG model of wireless Ad Hoc network

QIAN Jing?feng， YANG Qi

（School of Information Science and Technology， Xiamen University， Xiamen 361005， China）

Abstract： In the factors that affect wireless network synchronization， the network topology structure gradually draws attention of researchers. By studying the relationship between network clustering coefficient and the secondary largest eigenvalue in RGG model， the effect of network clustering coefficient on network convergence performance was explored under two conditions with and without boundary effect. Through the simulation， it is found that the clustering coefficient under the borderless condition is a constant， which is not related to other factors， and the clustering coefficient with boundary effect is related to the environment parameter. The theoretical value of clustering coefficient without boundary effect is derived theoretically. The thought of derivation with boundary effect is offered.

Keywords： Ad Hoc； network synchronization； topology structure； clustering coefficient

0 引 言

無(wú)線自組織（Ad Hoc）網(wǎng)絡(luò)是一組帶有無(wú)線通信收發(fā)裝置的移動(dòng)節(jié)點(diǎn)組成的一種對(duì)等的無(wú)中心分布式網(wǎng)絡(luò)。網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)既是路由節(jié)點(diǎn)，又是終端。所有的節(jié)點(diǎn)都是平等的，不存在中心節(jié)點(diǎn)。與傳統(tǒng)的網(wǎng)絡(luò)相比，無(wú)線自組織網(wǎng)絡(luò)具有組網(wǎng)靈活，接入快，抗毀能力強(qiáng)，不怕惡意攻擊等優(yōu)點(diǎn)，在軍事用途以及災(zāi)后救援方面，能夠第一時(shí)間架設(shè)組網(wǎng)，滿足通信需求。近年來(lái)在民用項(xiàng)目上也漸漸嶄露頭角[1]。尤其是在完成連續(xù)和無(wú)縫通信的要求上，Ad Hoc網(wǎng)絡(luò)將會(huì)成為Internet網(wǎng)絡(luò)重要的一個(gè)延伸點(diǎn)，可以應(yīng)用于與移動(dòng)通信和計(jì)算機(jī)網(wǎng)絡(luò)相結(jié)合的各種網(wǎng)絡(luò)需求上。憑著這些優(yōu)勢(shì)，無(wú)線自組織網(wǎng)絡(luò)已經(jīng)逐漸成為了眾多專(zhuān)家和學(xué)者廣泛關(guān)注和研究的熱點(diǎn)了[2]。

由于無(wú)線Ad Hoc網(wǎng)絡(luò)的通信是基于TDMA時(shí)隙分配多址接入原理的，但由于沒(méi)有中心節(jié)點(diǎn)，因此整個(gè)網(wǎng)絡(luò)的時(shí)間同步問(wèn)題便成了網(wǎng)絡(luò)通信需要解決的首要問(wèn)題。只有保證了整個(gè)網(wǎng)絡(luò)的時(shí)間的正確同步，才能實(shí)現(xiàn)信號(hào)的正確收發(fā)、控制以及數(shù)據(jù)的傳輸，也是協(xié)議正常運(yùn)作的一個(gè)基礎(chǔ)。

如何能夠快速并準(zhǔn)確地讓整個(gè)網(wǎng)絡(luò)的所有節(jié)點(diǎn)都收斂到同一個(gè)時(shí)間值，是眾多算法想要實(shí)現(xiàn)的一個(gè)目標(biāo)。近幾年對(duì)復(fù)雜網(wǎng)絡(luò)的研究發(fā)現(xiàn)，分布式網(wǎng)絡(luò)的收斂速度，和它的拓?fù)浣Y(jié)構(gòu)有著緊密的聯(lián)系[3?7]。網(wǎng)絡(luò)節(jié)點(diǎn)度分布、網(wǎng)絡(luò)熵、網(wǎng)絡(luò)半徑等參數(shù)都漸漸進(jìn)入各方的研究視野。作為表述網(wǎng)絡(luò)中節(jié)點(diǎn)與節(jié)點(diǎn)之間關(guān)系密切程度的一個(gè)量綱，聚類(lèi)系數(shù)至今卻鮮有人研究。因此，本文在RGG（Random Geometric Graph）模型的基礎(chǔ)上研究聚類(lèi)系數(shù)在有邊界、無(wú)邊界網(wǎng)絡(luò)等各種情況下的特性，分析其與收斂速度之間的關(guān)系。

1 聚類(lèi)系數(shù)與網(wǎng)絡(luò)收斂

1.1 聚類(lèi)系數(shù)

從廣義上來(lái)講，聚類(lèi)系數(shù)就是表示網(wǎng)絡(luò)中節(jié)點(diǎn)的鄰居之間關(guān)系緊密程度的一個(gè)系數(shù)。網(wǎng)絡(luò)中把一個(gè)節(jié)點(diǎn)通信范圍內(nèi)的其余節(jié)點(diǎn)都視為與這個(gè)節(jié)點(diǎn)連通，則這些節(jié)點(diǎn)就成了它的鄰居節(jié)點(diǎn)。假設(shè)一個(gè)節(jié)點(diǎn)[a]有[m]個(gè)鄰居節(jié)點(diǎn)，這[m]個(gè)鄰居之間相互又是鄰居的節(jié)點(diǎn)有[n]對(duì)，那么根據(jù)這個(gè)，聚類(lèi)系數(shù)的定義就是：

[Ra=nC2m=2nm（m-1）] （1）

即鄰居的節(jié)點(diǎn)互相成為鄰居的概率[8]。對(duì)于全網(wǎng)的平均聚類(lèi)系數(shù)，那就是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的聚類(lèi)系數(shù)的平均值[9]：

[R=1Ni∈NRi] （2）

很顯然聚類(lèi)系數(shù)[R]取值范圍在0～1之間。聚類(lèi)系數(shù)越大，則說(shuō)明節(jié)點(diǎn)的鄰居之間聯(lián)系越緊密，極端的情況就是當(dāng)聚類(lèi)系數(shù)為1時(shí)，網(wǎng)絡(luò)中所有節(jié)點(diǎn)都是兩兩互為鄰居。

1.2 次大特征值

網(wǎng)絡(luò)的收斂速度和網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)有很大關(guān)系[10]，而其中比較直觀的一個(gè)參數(shù)就是鄰接矩陣[A]轉(zhuǎn)化成拉普拉斯矩陣[L]后的特征值向量：

[L=D-A] （3）

式中[D]為網(wǎng)絡(luò)的度矩陣，對(duì)角線上為各個(gè)節(jié)點(diǎn)的度。

通過(guò)研究發(fā)現(xiàn)，拉普拉斯矩陣的特征值向量能夠反應(yīng)網(wǎng)絡(luò)收斂的性能，特別是次大特征值[λ2。][λ2]越小，網(wǎng)絡(luò)的收斂速度越快[11]。

因此便可以從次大特征值作為切入點(diǎn)來(lái)研究網(wǎng)絡(luò)的拓?fù)鋮?shù)對(duì)收斂速度的影響。

圖1通過(guò)數(shù)值仿真的方式展示了在網(wǎng)絡(luò)中節(jié)點(diǎn)均勻分布時(shí)，網(wǎng)絡(luò)的聚類(lèi)系數(shù)與次大特征值的關(guān)系?？梢钥闯?，隨著網(wǎng)絡(luò)中節(jié)點(diǎn)連通性的增大，即聚類(lèi)系數(shù)的增大，網(wǎng)絡(luò)的次大特征值越小。并且在不同的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)（密度）下，情況幾乎一樣。由圖1可以看出，網(wǎng)絡(luò)的聚類(lèi)系數(shù)越大，則網(wǎng)絡(luò)的收斂性能越佳。

圖1 均勻分布網(wǎng)絡(luò)中聚類(lèi)系數(shù)與次大特征值的關(guān)系

2 聚類(lèi)系數(shù)推導(dǎo)

本節(jié)將討論在無(wú)邊界情況下的聚類(lèi)系數(shù)的理論值，并給出有邊界情況下的推導(dǎo)思路。

首先假定網(wǎng)絡(luò)是無(wú)邊界的，網(wǎng)絡(luò)中有[N]個(gè)節(jié)點(diǎn)均勻分布，節(jié)點(diǎn)的通信半徑為[r。]由式（1）和式（2）可知，只要知道了網(wǎng)絡(luò)的節(jié)點(diǎn)分布概率密度，就可以求出每個(gè)節(jié)點(diǎn)的平均鄰居數(shù)，又由于節(jié)點(diǎn)是均勻分布的，則也可依概率求得節(jié)點(diǎn)間互為鄰居的概率。因此求平均聚類(lèi)系數(shù)，便等價(jià)于求一個(gè)節(jié)點(diǎn)的平均鄰居個(gè)數(shù)[m，]與鄰居中相互存在鏈路的概率[Pm]，即：

[R=C2m?PmC2m=Pm] （4）

式中：[Pm]為條件概率，即前提為節(jié)點(diǎn)[j，][k]均為節(jié)點(diǎn)[i]的鄰居，同時(shí)，節(jié)點(diǎn)[j]和[k]的距離又在通信半徑之內(nèi)。

如圖2所示，已知節(jié)點(diǎn)[j，][k]均為節(jié)點(diǎn)[i]的鄰居，那么[Pm]的概率即節(jié)點(diǎn)[k]落在陰影部分[S]中的概率。又由于節(jié)點(diǎn)[k]是均勻分布，且必定在[i]的通信范圍內(nèi)，那么：

[Pm=S（πr2）] （5）

其中[S]為陰影部分面積[S]的平均值。[φ]為圓心角，[l]為節(jié)點(diǎn)[i]和[j]的圓心距，由于對(duì)稱(chēng)性，因此只考慮半個(gè)圓之間里面的節(jié)點(diǎn)位置范圍，則[l∈（0，r），][φ∈（23π，π）]。

圖2 計(jì)算[Pm]結(jié)構(gòu)示意圖

陰影部分的面積：

[S=2φπr22π-r2sinφ2] （6）

因此只需要知道[φ]的概率密度函數(shù)來(lái)計(jì)算陰影部分的面積均值。這里設(shè)[l]的概率分布函數(shù)為[F（L）]，概率密度函數(shù)為[f（L），][φ]的概率分布函數(shù)為[G（Φ），]概率密度函數(shù)為[g（Φ）]，因此[cos （φ2）=l（2r），]因此[φ=2rarccosl。]由于[l=（xi-xj）2+（yi-yj）2]，而節(jié)點(diǎn)坐標(biāo)[（x，y）]又服從均勻分布，則[l]的概率分布函數(shù)為：

[F（L）=0，L≤0πL2πr2，0

根據(jù)定義有：

[G（Φ）=P（φ≤Φ）=P（2arccosL2r≤Φ）=P（2rcosΦ2≤L≤r）=F（r）-F2rcosΦ2=-2cosΦ-1 （8）]

因此，有：

[g（Φ）=?G（Φ）?Φ=2sinΦ] （9）

則根據(jù)式（6）可求得陰影部分平均面積：

[S=23ππS?g（Φ）dΦ=r2（π-334）] （10）

代入式（4），（5）可得平均聚類(lèi)系數(shù)：

[R=C2m?PmC2m=Pm=1-334π] （11）

通過(guò)理論證明發(fā)現(xiàn)，在無(wú)邊界情況下，均勻分布的網(wǎng)絡(luò)，其聚類(lèi)系數(shù)與節(jié)點(diǎn)密度、通信半徑等都沒(méi)關(guān)系，為恒定常數(shù)。這是因?yàn)樵诶硐肭闆r無(wú)邊界的條件下，網(wǎng)絡(luò)都是均勻分布的，因此聚類(lèi)系數(shù)也沒(méi)有差別。但實(shí)際情況肯定不存在無(wú)邊界，所有的網(wǎng)絡(luò)都是有邊界的，而且Ad Hoc網(wǎng)絡(luò)一般也不會(huì)很大到視為無(wú)邊界，所以比較有意義的還是在有邊界情況下的聚類(lèi)系數(shù)。

這里暫時(shí)給出理論推導(dǎo)有邊界情況下的聚類(lèi)系數(shù)的思路。不管網(wǎng)絡(luò)分布區(qū)域是圓形，還是矩形，將網(wǎng)絡(luò)分為[S1、][S2]兩個(gè)部分，如圖3所示。

圖3 有邊界網(wǎng)絡(luò)分割示意圖

圖3中，[S1]的邊界與外邊界的距離為節(jié)點(diǎn)的通信半徑[r，]則[S1]可視為是無(wú)邊界情況，里面的節(jié)點(diǎn)的聚類(lèi)系數(shù)即可用無(wú)邊界聚類(lèi)系數(shù)公式計(jì)算。剩下只要計(jì)算[S2]部分節(jié)點(diǎn)的平均聚類(lèi)系數(shù)就好了。

3 仿 真

3.1 無(wú)邊界情況

3.1.1 聚類(lèi)系數(shù)與節(jié)點(diǎn)密度

無(wú)邊界情況下，當(dāng)節(jié)點(diǎn)個(gè)數(shù)[N=40，80，…，400，]網(wǎng)絡(luò)半徑[R=0.5，]通信半徑[r=0.2]時(shí)，聚類(lèi)系數(shù)和節(jié)點(diǎn)個(gè)數(shù)的關(guān)系如圖4所示。從圖4中可以看到隨著節(jié)點(diǎn)密度的增加，網(wǎng)絡(luò)的平均聚類(lèi)系數(shù)是不變的，和理論計(jì)算值相吻合，從而驗(yàn)證了理論推導(dǎo)的正確性。

圖4 聚類(lèi)系數(shù)和節(jié)點(diǎn)個(gè)數(shù)的關(guān)系

3.1.2 聚類(lèi)系數(shù)與通信半徑

無(wú)邊界情況下，當(dāng)節(jié)點(diǎn)個(gè)數(shù)[N=]100，網(wǎng)絡(luò)半徑[R=]0.5，通信半徑[r=]0.1，0.2，0.3，0.4時(shí)，聚類(lèi)系數(shù)和通信半徑的關(guān)系如圖5所示。從圖5中可以看到，隨著網(wǎng)絡(luò)通信半徑的增加，網(wǎng)絡(luò)的平均聚類(lèi)系數(shù)基本保持不變，和理論值大致吻合。但可以看到，在網(wǎng)絡(luò)半徑較小時(shí)，網(wǎng)絡(luò)的連通性得不到保證，仿真值會(huì)有點(diǎn)偏差。

圖5 聚類(lèi)系數(shù)和通信半徑的關(guān)系

3.2 有邊界情況

3.2.1 聚類(lèi)系數(shù)與節(jié)點(diǎn)密度

圖6是在考慮邊界效應(yīng)情況下，節(jié)點(diǎn)個(gè)數(shù)[N=]25，30，…，180，通信半徑[r=]0.3，在不同網(wǎng)絡(luò)區(qū)域中考察節(jié)點(diǎn)密度與聚類(lèi)系數(shù)的關(guān)系。從圖中可以看出，有邊界情況下，無(wú)論是方形區(qū)域還是圓形區(qū)域，網(wǎng)絡(luò)的平均聚類(lèi)系數(shù)都不會(huì)因?yàn)楣?jié)點(diǎn)密度的變化而有太大變化（節(jié)點(diǎn)密度小時(shí)可能連通性不佳導(dǎo)致聚類(lèi)系數(shù)略有點(diǎn)?。?。且有邊界情況下的聚類(lèi)系數(shù)值趨于穩(wěn)定時(shí)，和無(wú)邊界情況相近。

3.2.2 聚類(lèi)系數(shù)與通信半徑

圖7是在考慮邊界的情況下，節(jié)點(diǎn)個(gè)數(shù)[N=]50，通信半徑[r=]0.2，0.21，0.22，…，1，在不同網(wǎng)絡(luò)區(qū)域中考察通信半徑與聚類(lèi)系數(shù)的關(guān)系。從圖中可以看出，隨著通信半徑的增大，網(wǎng)絡(luò)聚類(lèi)系數(shù)越來(lái)越趨于1，且在方形區(qū)域和圓形區(qū)域中趨勢(shì)是基本相同。相同通信半徑下，方形區(qū)域會(huì)比圓形區(qū)域網(wǎng)絡(luò)聚類(lèi)系數(shù)小，這是因?yàn)榉叫螀^(qū)域的面積略微比圓形區(qū)域大造成的?；究梢哉f(shuō)明在有邊界情況下聚類(lèi)系數(shù)與網(wǎng)絡(luò)形狀無(wú)關(guān)。

圖6 聚類(lèi)系數(shù)和節(jié)點(diǎn)個(gè)數(shù)的關(guān)系

圖7 聚類(lèi)系數(shù)和節(jié)點(diǎn)個(gè)數(shù)的關(guān)系

4 結(jié) 論

本文給出了聚類(lèi)系數(shù)在無(wú)邊界情況下的理論公式推導(dǎo)，并仿真證明其正確性。并給出了有邊界情況下的聚類(lèi)系數(shù)理論公式推導(dǎo)的指導(dǎo)思路。通過(guò)仿真發(fā)現(xiàn)，有邊界情況下，網(wǎng)絡(luò)的聚類(lèi)系數(shù)與網(wǎng)絡(luò)密度關(guān)系不大，但受節(jié)點(diǎn)通信半徑的影響很大。因此其理論公式很有可能與節(jié)點(diǎn)密度無(wú)關(guān)，而與節(jié)點(diǎn)通信半徑有關(guān)。

參考文獻(xiàn)

[1] 翟建華.Ad Hoc網(wǎng)絡(luò)接入機(jī)制與路由協(xié)議研究[D].重慶：重慶大學(xué)，2011.

[2] SIMEONE O， SPAGNOLINI U， BAR?NESS Y， et al. Distributed synchronization in wireless networks [J]. Signal Processing Magazine， IEEE， 2008， 25（5）： 81?97.

[3] 徐德剛.基于復(fù)雜網(wǎng)絡(luò)理論的復(fù)雜系統(tǒng)同步控制研究[D].杭州：浙江大學(xué)，2007.

[4] 汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2006.

[5] 王立夫.復(fù)雜網(wǎng)絡(luò)同步問(wèn)題的研究[D].沈陽(yáng)：東北大學(xué)，2010.

[6] TONG C， NIU J W， QU G Z， et al. Complex networks properties analysis for mobile Ad Hoc networks [J]. IET Communications， 2012， 6（4）： 370?380.

[7] PIECHOWIAK M， PUCEK S. Topology properties of Ad?hoc networks [M]. Heidelberg， Berlin： Springer， 2013.

[8] JALILI M. Synchronizability of dynamical scale?free networks subject to random errors [J]. Statistical Mechanics and its Applications， Physica A， 2011， 390（23）： 4588?4595.

[9] ARENAS A， D?AZ?GUILERA A， KURTHS J， et al. Synchronization in complex networks [J]. Physics Reports， 2008， 469（3）： 93?153.

[10] DE LIMA L S， NIKIFOROV V. On the second largest eigenvalue of the signless Laplacian [J]. Linear Algebra and Its Applications， 2013， 438（3）： 1215?1222.

[11] TONG C， NIU J W， QU G Z， et al. Complex networks properties analysis for mobile Ad Hoc networks [J]. IET communications， 2012， 6（4）： 370?380.

圖5 聚類(lèi)系數(shù)和通信半徑的關(guān)系

3.2 有邊界情況

3.2.1 聚類(lèi)系數(shù)與節(jié)點(diǎn)密度

圖6是在考慮邊界效應(yīng)情況下，節(jié)點(diǎn)個(gè)數(shù)[N=]25，30，…，180，通信半徑[r=]0.3，在不同網(wǎng)絡(luò)區(qū)域中考察節(jié)點(diǎn)密度與聚類(lèi)系數(shù)的關(guān)系。從圖中可以看出，有邊界情況下，無(wú)論是方形區(qū)域還是圓形區(qū)域，網(wǎng)絡(luò)的平均聚類(lèi)系數(shù)都不會(huì)因?yàn)楣?jié)點(diǎn)密度的變化而有太大變化（節(jié)點(diǎn)密度小時(shí)可能連通性不佳導(dǎo)致聚類(lèi)系數(shù)略有點(diǎn)?。Ｇ矣羞吔缜闆r下的聚類(lèi)系數(shù)值趨于穩(wěn)定時(shí)，和無(wú)邊界情況相近。

3.2.2 聚類(lèi)系數(shù)與通信半徑

圖7是在考慮邊界的情況下，節(jié)點(diǎn)個(gè)數(shù)[N=]50，通信半徑[r=]0.2，0.21，0.22，…，1，在不同網(wǎng)絡(luò)區(qū)域中考察通信半徑與聚類(lèi)系數(shù)的關(guān)系。從圖中可以看出，隨著通信半徑的增大，網(wǎng)絡(luò)聚類(lèi)系數(shù)越來(lái)越趨于1，且在方形區(qū)域和圓形區(qū)域中趨勢(shì)是基本相同。相同通信半徑下，方形區(qū)域會(huì)比圓形區(qū)域網(wǎng)絡(luò)聚類(lèi)系數(shù)小，這是因?yàn)榉叫螀^(qū)域的面積略微比圓形區(qū)域大造成的。基本可以說(shuō)明在有邊界情況下聚類(lèi)系數(shù)與網(wǎng)絡(luò)形狀無(wú)關(guān)。

圖6 聚類(lèi)系數(shù)和節(jié)點(diǎn)個(gè)數(shù)的關(guān)系

圖7 聚類(lèi)系數(shù)和節(jié)點(diǎn)個(gè)數(shù)的關(guān)系

4 結(jié) 論

本文給出了聚類(lèi)系數(shù)在無(wú)邊界情況下的理論公式推導(dǎo)，并仿真證明其正確性。并給出了有邊界情況下的聚類(lèi)系數(shù)理論公式推導(dǎo)的指導(dǎo)思路。通過(guò)仿真發(fā)現(xiàn)，有邊界情況下，網(wǎng)絡(luò)的聚類(lèi)系數(shù)與網(wǎng)絡(luò)密度關(guān)系不大，但受節(jié)點(diǎn)通信半徑的影響很大。因此其理論公式很有可能與節(jié)點(diǎn)密度無(wú)關(guān)，而與節(jié)點(diǎn)通信半徑有關(guān)。

參考文獻(xiàn)

[1] 翟建華.Ad Hoc網(wǎng)絡(luò)接入機(jī)制與路由協(xié)議研究[D].重慶：重慶大學(xué)，2011.

[2] SIMEONE O， SPAGNOLINI U， BAR?NESS Y， et al. Distributed synchronization in wireless networks [J]. Signal Processing Magazine， IEEE， 2008， 25（5）： 81?97.

[3] 徐德剛.基于復(fù)雜網(wǎng)絡(luò)理論的復(fù)雜系統(tǒng)同步控制研究[D].杭州：浙江大學(xué)，2007.

[4] 汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2006.

[5] 王立夫.復(fù)雜網(wǎng)絡(luò)同步問(wèn)題的研究[D].沈陽(yáng)：東北大學(xué)，2010.

[6] TONG C， NIU J W， QU G Z， et al. Complex networks properties analysis for mobile Ad Hoc networks [J]. IET Communications， 2012， 6（4）： 370?380.

[7] PIECHOWIAK M， PUCEK S. Topology properties of Ad?hoc networks [M]. Heidelberg， Berlin： Springer， 2013.

[8] JALILI M. Synchronizability of dynamical scale?free networks subject to random errors [J]. Statistical Mechanics and its Applications， Physica A， 2011， 390（23）： 4588?4595.

[9] ARENAS A， D?AZ?GUILERA A， KURTHS J， et al. Synchronization in complex networks [J]. Physics Reports， 2008， 469（3）： 93?153.

[10] DE LIMA L S， NIKIFOROV V. On the second largest eigenvalue of the signless Laplacian [J]. Linear Algebra and Its Applications， 2013， 438（3）： 1215?1222.

[11] TONG C， NIU J W， QU G Z， et al. Complex networks properties analysis for mobile Ad Hoc networks [J]. IET communications， 2012， 6（4）： 370?380.

圖5 聚類(lèi)系數(shù)和通信半徑的關(guān)系

3.2 有邊界情況

3.2.1 聚類(lèi)系數(shù)與節(jié)點(diǎn)密度

圖6是在考慮邊界效應(yīng)情況下，節(jié)點(diǎn)個(gè)數(shù)[N=]25，30，…，180，通信半徑[r=]0.3，在不同網(wǎng)絡(luò)區(qū)域中考察節(jié)點(diǎn)密度與聚類(lèi)系數(shù)的關(guān)系。從圖中可以看出，有邊界情況下，無(wú)論是方形區(qū)域還是圓形區(qū)域，網(wǎng)絡(luò)的平均聚類(lèi)系數(shù)都不會(huì)因?yàn)楣?jié)點(diǎn)密度的變化而有太大變化（節(jié)點(diǎn)密度小時(shí)可能連通性不佳導(dǎo)致聚類(lèi)系數(shù)略有點(diǎn)?。Ｇ矣羞吔缜闆r下的聚類(lèi)系數(shù)值趨于穩(wěn)定時(shí)，和無(wú)邊界情況相近。

3.2.2 聚類(lèi)系數(shù)與通信半徑

圖7是在考慮邊界的情況下，節(jié)點(diǎn)個(gè)數(shù)[N=]50，通信半徑[r=]0.2，0.21，0.22，…，1，在不同網(wǎng)絡(luò)區(qū)域中考察通信半徑與聚類(lèi)系數(shù)的關(guān)系。從圖中可以看出，隨著通信半徑的增大，網(wǎng)絡(luò)聚類(lèi)系數(shù)越來(lái)越趨于1，且在方形區(qū)域和圓形區(qū)域中趨勢(shì)是基本相同。相同通信半徑下，方形區(qū)域會(huì)比圓形區(qū)域網(wǎng)絡(luò)聚類(lèi)系數(shù)小，這是因?yàn)榉叫螀^(qū)域的面積略微比圓形區(qū)域大造成的?；究梢哉f(shuō)明在有邊界情況下聚類(lèi)系數(shù)與網(wǎng)絡(luò)形狀無(wú)關(guān)。

圖6 聚類(lèi)系數(shù)和節(jié)點(diǎn)個(gè)數(shù)的關(guān)系

圖7 聚類(lèi)系數(shù)和節(jié)點(diǎn)個(gè)數(shù)的關(guān)系

4 結(jié) 論

本文給出了聚類(lèi)系數(shù)在無(wú)邊界情況下的理論公式推導(dǎo)，并仿真證明其正確性。并給出了有邊界情況下的聚類(lèi)系數(shù)理論公式推導(dǎo)的指導(dǎo)思路。通過(guò)仿真發(fā)現(xiàn)，有邊界情況下，網(wǎng)絡(luò)的聚類(lèi)系數(shù)與網(wǎng)絡(luò)密度關(guān)系不大，但受節(jié)點(diǎn)通信半徑的影響很大。因此其理論公式很有可能與節(jié)點(diǎn)密度無(wú)關(guān)，而與節(jié)點(diǎn)通信半徑有關(guān)。

參考文獻(xiàn)

[1] 翟建華.Ad Hoc網(wǎng)絡(luò)接入機(jī)制與路由協(xié)議研究[D].重慶：重慶大學(xué)，2011.

[2] SIMEONE O， SPAGNOLINI U， BAR?NESS Y， et al. Distributed synchronization in wireless networks [J]. Signal Processing Magazine， IEEE， 2008， 25（5）： 81?97.

[3] 徐德剛.基于復(fù)雜網(wǎng)絡(luò)理論的復(fù)雜系統(tǒng)同步控制研究[D].杭州：浙江大學(xué)，2007.

[4] 汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2006.

[5] 王立夫.復(fù)雜網(wǎng)絡(luò)同步問(wèn)題的研究[D].沈陽(yáng)：東北大學(xué)，2010.

[6] TONG C， NIU J W， QU G Z， et al. Complex networks properties analysis for mobile Ad Hoc networks [J]. IET Communications， 2012， 6（4）： 370?380.

[7] PIECHOWIAK M， PUCEK S. Topology properties of Ad?hoc networks [M]. Heidelberg， Berlin： Springer， 2013.

[8] JALILI M. Synchronizability of dynamical scale?free networks subject to random errors [J]. Statistical Mechanics and its Applications， Physica A， 2011， 390（23）： 4588?4595.

[9] ARENAS A， D?AZ?GUILERA A， KURTHS J， et al. Synchronization in complex networks [J]. Physics Reports， 2008， 469（3）： 93?153.

[10] DE LIMA L S， NIKIFOROV V. On the second largest eigenvalue of the signless Laplacian [J]. Linear Algebra and Its Applications， 2013， 438（3）： 1215?1222.

[11] TONG C， NIU J W， QU G Z， et al. Complex networks properties analysis for mobile Ad Hoc networks [J]. IET communications， 2012， 6（4）： 370?380.