Page 246 - 《软件学报》2020年第11期

于冲 等:基于二跳共同邻居的无人机群体网络演化算法 3561

T C _( , )x y = ∑ C N _( , )z y (1)
zE x ,z y
≠
∈
值得注意的是,节点 x 与节点 y 度值具有不对称性,导致 E x 并不等同于 E y ,因此 T C_(x,y) ≠T C_(y,x) .通过公式(1)
我们能够发现,T C_(x,y) 与 C N_(z,y) 成正相关关系,C N_(z,y) 表示节点 z 与节点 y 的相似性,那么 T C_(x,y) 则可表示为邻居
集 E x 与节点 y 的相似性.
假设有 N 个通信半径为 R 的节点随机散布在边长为 L 的三维空间中,并且节点 z 在节点 y 的通信范围内.
定义节点 z 与节点 y 之间的期望距离为 d .由于节点是随机分布的,所以节点 z 在节点 y 通信范围内任何一个位
3
置上的概率相同,因而期望距离 d 与节点 y 的通信范围 4πR /3 满足如下关系:
4 3 1 4 3
π d = ⋅ π R (2)
3 2 3
节点 z 与节点 y 的空间位置关系如图 1 所示.
A

X H Q Y

B

Fig.1 Spatial location relations of nodes
图 1 节点空间位置关系
通过图 1 可知,节点 z 与节点 y 的通信区域重叠范围为椭球体 AHBQ.根据空间几何学知识,我们可以得到
V AHBQ =2(V XAQB −V XAB )=2(V YAHB −V YAB ),由此,我们能够计算出两个节点之间的平均重叠范围为
2 2/3(R d−
Ω =⋅ / 2) Rπ 2 − 2/3 (Rπ 2 − ( / 2) ) / 2 0.581d 2 d = π R 3 (3)
3
由于空间中节点的密度为ρ=N/L ,则两个节点之间的平均共同邻居数可以表示为
C N_average =Ωρ=NΩ/L 3 (4)
E x ,1≤x≤N 中,节点个数的平均值可以用网络中节点的度值平均值 k 表示.基于二跳共同邻居的基本定义,
我们可以近似地将平均二跳共同邻居看作网络中节点的平均度值 k 与平均共同邻居数 C N_average 的乘积,故有:
T C _ average ≈ k C⋅ N _ average = k NΩ⋅ / L 3 (5)
−α
许多复杂网络度分布规律符合 P(k)=ck ,α∈(2,3),文献[17]推导出部分复杂网络中最大度值 k max 与最小度
1
值 k min 的关系为 k max ≈ k min N α − 1 ,文献[18]计算得到微分方程常数项 c 与最小度 k min 的关系为 c ≈ (α − 1)k α − 1 .根据
min
上述信息,我们能够推导出:
max
T C _ average k NΩ = ⋅ / L = 3 NΩ / L 3 k ∫ k min kP ( )dk k
= NΩ / L 3 k ∫ k max ck 1 α− dk
min c (6)
= NΩ / L 3 (k 2 α − − k 2 α − )
2 α− max min
3 α − 1 ⎛ 2 α− ⎞
= NΩ / L k min ⎜ N α − 1 − 1⎟
2 α ⎜ ⎝ ⎟ ⎠
−
1.2 二跳共同邻居指标分析
在节点总数为 100、节点分布区域边长为 1000m、通信半径为 500m、最小度值为 1 的条件下,描绘平均
二跳共同邻居与度分布指数α的关系图,其结果如图 2 所示.