TATbed无线自组织网络测试平台设计与实现

钱静丰+杨琦

摘 要： 在影响无线网络同步的因素中，网络拓扑结构逐渐引起人们的关注。通过研究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.