無線自組織網絡RGG模型聚類系數研究

錢靜豐+楊琦

摘 要： 在影響無線網絡同步的因素中，網絡拓撲結構逐漸引起人們的關注。通過研究RGG模型中網絡聚類系數和網絡次大特征值之間的關系，來探索聚類系數對網絡收斂性能的影響程度，并希望從有邊界效應和無邊界效應兩種情況入手對其進行研究。通過仿真實驗發現在無邊界情況下的聚類系數是一個常數，與其他因素無關，有邊界情況下其值與環境參數相關。從理論上推導了無邊界聚類系數的理論值，并給出了有邊界情況下的推導思路。

關鍵詞： Ad Hoc； 網絡同步； 拓撲結構； 聚類系數

中圖分類號： TN92?34 文獻標識碼： A 文章編號： 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 引 言

無線自組織（Ad Hoc）網絡是一組帶有無線通信收發裝置的移動節點組成的一種對等的無中心分布式網絡。網絡中的每個節點既是路由節點，又是終端。所有的節點都是平等的，不存在中心節點。與傳統的網絡相比，無線自組織網絡具有組網靈活，接入快，抗毀能力強，不怕惡意攻擊等優點，在軍事用途以及災后救援方面，能夠第一時間架設組網，滿足通信需求。近年來在民用項目上也漸漸嶄露頭角[1]。尤其是在完成連續和無縫通信的要求上，Ad Hoc網絡將會成為Internet網絡重要的一個延伸點，可以應用于與移動通信和計算機網絡相結合的各種網絡需求上。憑著這些優勢，無線自組織網絡已經逐漸成為了眾多專家和學者廣泛關注和研究的熱點了[2]。

由于無線Ad Hoc網絡的通信是基于TDMA時隙分配多址接入原理的，但由于沒有中心節點，因此整個網絡的時間同步問題便成了網絡通信需要解決的首要問題。只有保證了整個網絡的時間的正確同步，才能實現信號的正確收發、控制以及數據的傳輸，也是協議正常運作的一個基礎。

如何能夠快速并準確地讓整個網絡的所有節點都收斂到同一個時間值，是眾多算法想要實現的一個目標。近幾年對復雜網絡的研究發現，分布式網絡的收斂速度，和它的拓撲結構有著緊密的聯系[3?7]。網絡節點度分布、網絡熵、網絡半徑等參數都漸漸進入各方的研究視野。作為表述網絡中節點與節點之間關系密切程度的一個量綱，聚類系數至今卻鮮有人研究。因此，本文在RGG（Random Geometric Graph）模型的基礎上研究聚類系數在有邊界、無邊界網絡等各種情況下的特性，分析其與收斂速度之間的關系。

1 聚類系數與網絡收斂

1.1 聚類系數

從廣義上來講，聚類系數就是表示網絡中節點的鄰居之間關系緊密程度的一個系數。網絡中把一個節點通信范圍內的其余節點都視為與這個節點連通，則這些節點就成了它的鄰居節點。假設一個節點[a]有[m]個鄰居節點，這[m]個鄰居之間相互又是鄰居的節點有[n]對，那么根據這個，聚類系數的定義就是：

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

即鄰居的節點互相成為鄰居的概率[8]。對于全網的平均聚類系數，那就是網絡中所有節點的聚類系數的平均值[9]：

[R=1Ni∈NRi] （2）

很顯然聚類系數[R]取值范圍在0～1之間。聚類系數越大，則說明節點的鄰居之間聯系越緊密，極端的情況就是當聚類系數為1時，網絡中所有節點都是兩兩互為鄰居。

1.2 次大特征值

網絡的收斂速度和網絡的拓撲結構有很大關系[10]，而其中比較直觀的一個參數就是鄰接矩陣[A]轉化成拉普拉斯矩陣[L]后的特征值向量：

[L=D-A] （3）

式中[D]為網絡的度矩陣，對角線上為各個節點的度。

通過研究發現，拉普拉斯矩陣的特征值向量能夠反應網絡收斂的性能，特別是次大特征值[λ2。][λ2]越小，網絡的收斂速度越快[11]。

因此便可以從次大特征值作為切入點來研究網絡的拓撲參數對收斂速度的影響。

圖1通過數值仿真的方式展示了在網絡中節點均勻分布時，網絡的聚類系數與次大特征值的關系。可以看出，隨著網絡中節點連通性的增大，即聚類系數的增大，網絡的次大特征值越小。并且在不同的網絡節點數（密度）下，情況幾乎一樣。由圖1可以看出，網絡的聚類系數越大，則網絡的收斂性能越佳。

圖1 均勻分布網絡中聚類系數與次大特征值的關系

2 聚類系數推導

本節將討論在無邊界情況下的聚類系數的理論值，并給出有邊界情況下的推導思路。

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

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

式中：[Pm]為條件概率，即前提為節點[j，][k]均為節點[i]的鄰居，同時，節點[j]和[k]的距離又在通信半徑之內。

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

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

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

圖2 計算[Pm]結構示意圖

陰影部分的面積：

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

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

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

根據定義有：

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

因此，有：

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

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

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

代入式（4），（5）可得平均聚類系數：

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

通過理論證明發現，在無邊界情況下，均勻分布的網絡，其聚類系數與節點密度、通信半徑等都沒關系，為恒定常數。這是因為在理想情況無邊界的條件下，網絡都是均勻分布的，因此聚類系數也沒有差別。但實際情況肯定不存在無邊界，所有的網絡都是有邊界的，而且Ad Hoc網絡一般也不會很大到視為無邊界，所以比較有意義的還是在有邊界情況下的聚類系數。

這里暫時給出理論推導有邊界情況下的聚類系數的思路。不管網絡分布區域是圓形，還是矩形，將網絡分為[S1、][S2]兩個部分，如圖3所示。

圖3 有邊界網絡分割示意圖

圖3中，[S1]的邊界與外邊界的距離為節點的通信半徑[r，]則[S1]可視為是無邊界情況，里面的節點的聚類系數即可用無邊界聚類系數公式計算。剩下只要計算[S2]部分節點的平均聚類系數就好了。

3 仿 真

3.1 無邊界情況

3.1.1 聚類系數與節點密度

無邊界情況下，當節點個數[N=40，80，…，400，]網絡半徑[R=0.5，]通信半徑[r=0.2]時，聚類系數和節點個數的關系如圖4所示。從圖4中可以看到隨著節點密度的增加，網絡的平均聚類系數是不變的，和理論計算值相吻合，從而驗證了理論推導的正確性。

圖4 聚類系數和節點個數的關系

3.1.2 聚類系數與通信半徑

無邊界情況下，當節點個數[N=]100，網絡半徑[R=]0.5，通信半徑[r=]0.1，0.2，0.3，0.4時，聚類系數和通信半徑的關系如圖5所示。從圖5中可以看到，隨著網絡通信半徑的增加，網絡的平均聚類系數基本保持不變，和理論值大致吻合。但可以看到，在網絡半徑較小時，網絡的連通性得不到保證，仿真值會有點偏差。

圖5 聚類系數和通信半徑的關系

3.2 有邊界情況

3.2.1 聚類系數與節點密度

圖6是在考慮邊界效應情況下，節點個數[N=]25，30，…，180，通信半徑[r=]0.3，在不同網絡區域中考察節點密度與聚類系數的關系。從圖中可以看出，有邊界情況下，無論是方形區域還是圓形區域，網絡的平均聚類系數都不會因為節點密度的變化而有太大變化（節點密度小時可能連通性不佳導致聚類系數略有點小）。且有邊界情況下的聚類系數值趨于穩定時，和無邊界情況相近。

3.2.2 聚類系數與通信半徑

圖7是在考慮邊界的情況下，節點個數[N=]50，通信半徑[r=]0.2，0.21，0.22，…，1，在不同網絡區域中考察通信半徑與聚類系數的關系。從圖中可以看出，隨著通信半徑的增大，網絡聚類系數越來越趨于1，且在方形區域和圓形區域中趨勢是基本相同。相同通信半徑下，方形區域會比圓形區域網絡聚類系數小，這是因為方形區域的面積略微比圓形區域大造成的。基本可以說明在有邊界情況下聚類系數與網絡形狀無關。

圖6 聚類系數和節點個數的關系

圖7 聚類系數和節點個數的關系

4 結 論

本文給出了聚類系數在無邊界情況下的理論公式推導，并仿真證明其正確性。并給出了有邊界情況下的聚類系數理論公式推導的指導思路。通過仿真發現，有邊界情況下，網絡的聚類系數與網絡密度關系不大，但受節點通信半徑的影響很大。因此其理論公式很有可能與節點密度無關，而與節點通信半徑有關。

參考文獻

[1] 翟建華.Ad Hoc網絡接入機制與路由協議研究[D].重慶：重慶大學，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] 徐德剛.基于復雜網絡理論的復雜系統同步控制研究[D].杭州：浙江大學，2007.

[4] 汪小帆，李翔，陳關榮.復雜網絡理論及其應用[M].北京：清華大學出版社，2006.

[5] 王立夫.復雜網絡同步問題的研究[D].沈陽：東北大學，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 聚類系數和通信半徑的關系

3.2 有邊界情況

3.2.1 聚類系數與節點密度

圖6是在考慮邊界效應情況下，節點個數[N=]25，30，…，180，通信半徑[r=]0.3，在不同網絡區域中考察節點密度與聚類系數的關系。從圖中可以看出，有邊界情況下，無論是方形區域還是圓形區域，網絡的平均聚類系數都不會因為節點密度的變化而有太大變化（節點密度小時可能連通性不佳導致聚類系數略有點小）。且有邊界情況下的聚類系數值趨于穩定時，和無邊界情況相近。

3.2.2 聚類系數與通信半徑

圖7是在考慮邊界的情況下，節點個數[N=]50，通信半徑[r=]0.2，0.21，0.22，…，1，在不同網絡區域中考察通信半徑與聚類系數的關系。從圖中可以看出，隨著通信半徑的增大，網絡聚類系數越來越趨于1，且在方形區域和圓形區域中趨勢是基本相同。相同通信半徑下，方形區域會比圓形區域網絡聚類系數小，這是因為方形區域的面積略微比圓形區域大造成的。基本可以說明在有邊界情況下聚類系數與網絡形狀無關。

圖6 聚類系數和節點個數的關系

圖7 聚類系數和節點個數的關系

4 結 論

本文給出了聚類系數在無邊界情況下的理論公式推導，并仿真證明其正確性。并給出了有邊界情況下的聚類系數理論公式推導的指導思路。通過仿真發現，有邊界情況下，網絡的聚類系數與網絡密度關系不大，但受節點通信半徑的影響很大。因此其理論公式很有可能與節點密度無關，而與節點通信半徑有關。

參考文獻

[1] 翟建華.Ad Hoc網絡接入機制與路由協議研究[D].重慶：重慶大學，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] 徐德剛.基于復雜網絡理論的復雜系統同步控制研究[D].杭州：浙江大學，2007.

[4] 汪小帆，李翔，陳關榮.復雜網絡理論及其應用[M].北京：清華大學出版社，2006.

[5] 王立夫.復雜網絡同步問題的研究[D].沈陽：東北大學，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 聚類系數和通信半徑的關系

3.2 有邊界情況

3.2.1 聚類系數與節點密度

圖6是在考慮邊界效應情況下，節點個數[N=]25，30，…，180，通信半徑[r=]0.3，在不同網絡區域中考察節點密度與聚類系數的關系。從圖中可以看出，有邊界情況下，無論是方形區域還是圓形區域，網絡的平均聚類系數都不會因為節點密度的變化而有太大變化（節點密度小時可能連通性不佳導致聚類系數略有點小）。且有邊界情況下的聚類系數值趨于穩定時，和無邊界情況相近。

3.2.2 聚類系數與通信半徑

圖7是在考慮邊界的情況下，節點個數[N=]50，通信半徑[r=]0.2，0.21，0.22，…，1，在不同網絡區域中考察通信半徑與聚類系數的關系。從圖中可以看出，隨著通信半徑的增大，網絡聚類系數越來越趨于1，且在方形區域和圓形區域中趨勢是基本相同。相同通信半徑下，方形區域會比圓形區域網絡聚類系數小，這是因為方形區域的面積略微比圓形區域大造成的。基本可以說明在有邊界情況下聚類系數與網絡形狀無關。

圖6 聚類系數和節點個數的關系

圖7 聚類系數和節點個數的關系

4 結 論

本文給出了聚類系數在無邊界情況下的理論公式推導，并仿真證明其正確性。并給出了有邊界情況下的聚類系數理論公式推導的指導思路。通過仿真發現，有邊界情況下，網絡的聚類系數與網絡密度關系不大，但受節點通信半徑的影響很大。因此其理論公式很有可能與節點密度無關，而與節點通信半徑有關。

參考文獻

[1] 翟建華.Ad Hoc網絡接入機制與路由協議研究[D].重慶：重慶大學，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] 徐德剛.基于復雜網絡理論的復雜系統同步控制研究[D].杭州：浙江大學，2007.

[4] 汪小帆，李翔，陳關榮.復雜網絡理論及其應用[M].北京：清華大學出版社，2006.

[5] 王立夫.復雜網絡同步問題的研究[D].沈陽：東北大學，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.