机会传感网络中,节点移动导致其连通度呈动态变化,使得应用于静态网络的连通度研究方法不能直接应用于机会传感网络,针对机会传感网络的特点刻画网络连通程度尤为重要. 为此,定义了区域连通度和Ferry节点连通度,分析其影响因素,通过实验,采用灰关联分析法筛选出主要因素. 通过逐步回归分析对区域连通度和Ferry节点连通度进行拟合,获得数学模型,在此基础上构建了网络连通度模型,为刻画网络连通度提供了依据. 实验结果表明,该网络连通度模型能够较好地反映网络的连通性.
Connectivity and guarantee of communication is important for networks. In opportunistic sensor networks (OSNs), the dynamic connectivity leads to the fact that methods applied to research the static networks are unsuitable for OSNs. It is significant for the connectivity by analyzing the network features. For building a connectivity model of OSNs, the concepts of regional connectivity (RC) and the Ferry connectivity (FC) were defined, and their influencing factors were analyzed. The major factors were selected by using gray relation analysis (GRA) based on large number of experiment data. Furthermore, the mathematical definitions of RC and FC were obtained by regression analysis. In terms of RC and FC, the network connectivity model is constructed, which provides the basis for describing the network connectivity. Experiment shows that the proposed connectivity model can describe the connectivity of OSNs preferably.
由于网络结构不断变化，机会传感网络中的节点随之不断连接、断开和重连，节点连接具有机会性[1]、间歇性；运行一段时间后，因能量、故障等原因易造成节点失效，网络拓扑的改变将更大、更频繁，导致网络的连通具有更强的动态性[2]，如图 1所示. 利用船只收集湖泊区域的环境信息、利用无人机收集战场信息等是本研究的应用场景，如何对其进行建模，进而监视其连通性是本研究需要解决的关键问题.
|
图1 多区域机会传感网络模型 |
目前，机会传感网络连通性的研究集中在基于移动模型的研究[3]、基于特征值的研究[4]和基于随机图的研究[5]. 上述研究大多针对优化网络设计，笔者研究机会传感网络连通性度量，从区域连通度、Ferry节点连通度等研究机会传感网络的连通性.
1 机会传感网络连通度影响因素 1.1 区域连通度和Ferry节点连通度转发效率是衡量网络连通程度的重要标准[6]，消息时延能够直接体现网络转发效率，笔者采用时延定义区域连通度和Ferry节点连通度.
定义1 区域连通度(RC,regional connectivity)为Rc，表示区域节点将消息转发给Ferry节点的平均效率. 若区域内节点的平均消息时延为B，最大值即生存时间(TTL，time to live)为L，则区域连通度为
| $ {R_{\rm{c}}} = 1 - \frac{B}{L} $ | (1) |
定义区域凝聚度为区域内节点间交流的程度，区域活跃度为区域节点与Ferry节点的交互程度.
定义2 Ferry节点连通度(FC，Ferry connectivity)为Fc，表示Ferry节点在网络中对各区域消息的平均转发效率. 若Ferry节点时延为P，最大值为L，则Ferry节点连通度为
| $ {F_{\rm{c}}} = 1 - \frac{P}{L} $ | (2) |
定义Ferry节点的层次：与Sink节点直接相遇的Ferry节点划分为第1层，与第1层Ferry节点相遇的Ferry节点为第2层，以此类推.
1.2 区域连通度影响因素影响区域凝聚度的因素包括区域节点密度RDensity、区域节点数RNode、区域面积RArea、区域节点的平均移动速度RVelocity、区域节点的通信半径RRadius；影响区域活跃度的因素包括区域内节点到Ferry节点的平均转发次数RForward、区域内节点到Ferry节点的平均投递概率RDelivery、区域内节点与Ferry节点的相遇概率RContact.
笔者采用机会传感网络仿真工具(ONE,opportunistic network environment simulator)进行实验，通过灰关联分析得到各因素之间的灰关联度，最终筛选出主要影响因素.
1) 实验设计
设计实验场景和实验参数如图 2和表 1所示.
|
图2 区域连通度影响因素实验模型 |
 | 表1 区域连通度影响因素实验参数 |
2) 灰关联分析
RNode与其他因素的灰关联度分析结果如表 2所示，RDensity、RDelivery、RForward和RNode之间的灰关联度均在0.98以上，相关性较大，因此将这3个因素剔除.
| 表2 节点数与其他因素的灰关联度 |
RVelocity与RContact、RVelocity与RRadius的灰关联度分析结果如表 3所示，RVelocity与其他2个因素的灰关联度均小于0.9，相关性较小，因此被保留.
| 表3 节点速度与其他因素的灰关联度 |
综上所述，利用灰关联度分析法得到影响区域连通度的主要因素为RNode、RVelocity、RRadius、RContact.
1.3 Ferry节点连通度影响因素Ferry节点连通度影响因素为Ferry节点所处的层数FLayer、Ferry节点与上一层节点的相遇概率FContact，其分析过程与区域连通度类似.
2 机会传感网络连通度回归分析在上述实验的基础上，采用回归分析法对区域连通度和Ferry节点连通度进行拟合，得到它们与影响因素之间的关系.
2.1 区域连通度的回归分析为准确分析主要因素对区域连通度的影响，设计3组实验场景为改变RNode、改变RVelocity、改变RRadius，得到RNode、RVelocity、RRadius、RContact与Rd的关系如图 3所示.
|
图3 主要因素与区域时延的关系 |
由图 3(a)可知，当RNode小于10时，随着节点数的增加，区域时延增加；当RNode大于15时，随着节点数的增加，区域时延减小. 当节点数较少时，节点可通过较少的转发次数将消息转发给Ferry节点，当单次转发时延一定时，更少的区域节点转发次数使得区域时延较小，随着RNode的增加，转发次数增加，时延也增加，此时影响区域时延的决定因素为消息转发次数；当RNode增加到一定程度时，RContact增大，引起区域时延的缓慢下降，此时影响区域时延的决定因素为RContact.
由图 3(b)可知，随着RVelocity的增加，区域时延减少，但是当RVelocity大于3.0时，区域时延有所增加. 因为当RVelocity较低时，增加RVelocity能够增加节点间的通信机会，区域时延随之降低；但当RVelocity持续增加时，在一次通信机会里，节点的可利用通信时间减少，节点还没有完成1次消息交换，节点间的连接就已经断开，因此区域时延随之增加.
由图 3(c)可知，RRadius越大，区域时延越低. RRadius的增加，不但使得区域节点与Ferry节点的相遇机会增多，还导致区域内节点间具有更多通信机会，从两方面降低了区域时延.
由图 3(d)可知，区域时延随着RContact的增加而减少，这是因为区域节点有更多机会将消息转发给Ferry节点，从而降低区域时延.
利用统计产品与服务解决方案(SPSS，statistical product and service solutions)对区域时延影响因素进行拟合的结果如表 4所示. 通过逐步回归分析，T-检验的结果表明，RRadius没有单独存在的必要，因此被移除.
| 表4 对区域时延影响因素的拟合结果 |
从表 4可知，RNode、RVelocity、RContact对应的显著性检验(Sig，significance test)近似为0，表明它们和区域时延均存在线性关系，得到拟合公式为
| $ \begin{array}{*{20}{c}} {B = 0.045{R_{{\rm{Node}}}} - 9.6.6{R_{{\rm{Contact}}}} - }\\ {1.583{R_{{\rm{Velocity}}}} + 19.165} \end{array} $ | (3) |
实验分析过程与2.1节类似，得到拟合公式为
| $ P = 26.152{F_{{\rm{Layer}}}} - 238.366{F_{{\rm{Contact}}}} + 10.093 $ | (4) |
由图 1可知，具有相同连通度的区域，直接与第1层Ferry节点相遇的区域对整网连通度的贡献大于不能直接与第1层Ferry节点相遇的区域. 消息由区域节点转发到Sink节点所产生的时延与区域连通度和Ferry节点连通度紧密相关，区域时延由式(3)计算，Ferry节点时延由式(4)计算.
直接与第1层Ferry节点相遇的区域，用式(5)计算该区域的区域连通度和穿过该区域的所有Ferry节点的Ferry节点连通度.
| $ s\left( j \right) = L\left( {1 - R\left( {i,j} \right)} \right) + \frac{1}{{\sum\limits_{x = 1} {\frac{1}{{L\left( {1 - F\left( {i,j,x} \right)} \right)}}} }} $ | (5) |
其中：R(i,j)为第i个网络快照中区域j的区域连通度，L(1-R(i,j))为区域j的区域时延，F(i,j,x)为协助区域j转发消息的Ferry节点x在第i个网络快照中的Ferry节点连通度，L(1-F(i,j,x))为Ferry节点x在第i个网络快照中的Ferry节点时延，w为计算区域j的消息从Ferry节点到Sink节点的时延期望.
不能直接与第1层Ferry节点相遇的区域，用式(6)计算该区域的区域连通度和穿过该区域的所有Ferry节点的Ferry节点连通度.
| $ h\left( k \right) = s\left( k \right){w^g},\;w \ge 1,\;g \ge 1 $ | (6) |
其中：区域k在最后1次连通快照时，s(k)由式(5)计算得到；wg为惩罚因子，g为距最后1次连通快照的快照间隔数，即退化代数. 网络运行过程中，可能出现部分连通的情况，由于无法获取与Sink节点不连通区域的相关信息，所以需要引入退化机制，参考其历史快照，并假设其在最后1次连通程度下以退化率w退化，得到式(6).
在机会传感网络中，受Ferry节点的影响，连通区域可能转化为不连通区域，不连通区域也可能转化为连通区域. 因此，连通性模型需要每经过t时间就进行1次网络快照，求出各区域连通度和各Ferry节点连通度，经过$\left\lceil {T/t} \right\rceil $次网络快照后，将其均值作为最近T时间段内的网络连通度. 由式(5)和式(6)，得到网络连通度为
| $ D = 1 - \frac{{\sum\limits_{i = 1}^{\left\lceil {T/t} \right\rceil } {\left( {\sum\limits_{j \in C} {s\left( j \right) + \sum\limits_{k \in N} {h\left( k \right)} } } \right)} }}{{n\left\lceil {T/t} \right\rceil L}} $ | (7) |
其中：n为区域数，t为网络快照时间间隔，T为连通性模型计算周期，i为在1个计算周期内的第i个网络快照，C为连通区域集，N为不连通区域集，减号右边的部分为消息从区域节点发送至Sink节点的实际平均时延，取值为(0,L]，表示最大可能时延与实际时延的差值，差值越大，时延越小，即网络的连通程度越好.
3.2 网络连通度实验设计设计3组实验，实验场景如图 4所示，其中不规则曲线为Ferry移动轨迹，区域内实验参数如表 1所示.
|
图4 网络连通度实验场景 |
实验1 网络连通度较差的场景. Sink节点处于图 4中的c位置，Ferry节点fc14与Sink节点直接相遇，fa12、fb13需要通过fc14的转发才能将消息发送给Sink节点.
实验2 网络连通度一般的场景. Sink节点处于图 4中的b位置，Ferry节点fc14、fb13直接与Sink节点相遇，fa12需要通过fc14的转发才能将消息发送给Sink节点.
实验3 网络连通度较好的场景. Sink节点处于图 4中的a位置，Ferry节点fc14、fb13和fa12直接与Sink节点相遇.
3.3 网络连通度实验分析通过实验1，采集得到RNode、RContact和RVelocity，由式(3)和式(1)得到各区域的区域连通度如图 5所示，通过采集得到各区域的区域时延如图 6所示.
|
图5 各区域的区域连通度 |
|
图6 各区域的区域时延 |
由图 5可知，rc区域连通度最高，均值为0.950 2，ra区域连通度次之，均值为0.921 7，rb区域连通度均值为0.920 0，rd区域连通度最差，均值为0.918 3. 由图 6可知，rc区域时延最低，均值为9.953 6，ra区域时延略高，均值为15.666 0，rb区域时延均值为16.007 1，rd区域时延最高，均值为16.330 1. 可见，时延高的区域，区域连通度低；时延低的区域，区域连通度高. 笔者定义的区域连通度能够反映区域的连通程度.
通过实验1，采集得到FLayer和FContact，由式(2)和式(4)计算得到Ferry节点连通度如 图 7所示，采集得到Ferry节点时延如图 8所示.
|
图7 Ferry节点连通度 |
|
图8 各Ferry节点时延 |
由图 7可知，fa的Ferry节点连通度最低，均值为0.830 3，fc的Ferry节点连通度均值为0.872 6，fb的Ferry节点连通度最高，均值为0.974 0. fa和fc的Ferry节点连通度波动幅度较大，fb的Ferry节点时延波动较小，集中在0.96以上，这是由于fb所处层次为1，与Sink节点直接相遇，fa和fc所处层次为2，所以fa和fc的Ferry节点连通度波动性较大.
由图 8可知，fa的Ferry节点时延最高，均值为33.946 7，fc的Ferry节点时延均值为25.473 8，fb的Ferry节点时延最低，均值为5.206 3，fa和fc的Ferry节点时延波动幅度较大，有些达到200. 可见，连通度高的Ferry节点，其对应的时延低；连通度低的Ferry节点，其对应的时延高. 因此，笔者定义的Ferry节点连通度能够反映Ferry节点的携带转发能力. 此外，连通度波动幅度较大的Ferry节点，其对应的时延波动也较大，这也验证了笔者定义的Ferry节点连通度的合理性.
设退化因子w=1.1，由式(7)计算得到网络连通度如图 9所示.
|
图9 3组实验网络连通度对比 |
由图 9可知，图例为“×”的连通性最低，图例为“○”的连通性一般，图例为“*”的连通性最好. 可见，由笔者提出的连通性模型计算得到的网络连通度与实验场景设定的网络连通情况吻合. 因此，笔者提出的网络连通性模型能够反映出多区域机会传感网络的连通程度.
4 结束语针对机会传感网络特点，定义了区域连通度和Ferry节点连通度，分析了影响区域连通度和Ferry节点连通度的因素，通过大量实验获得区域连通度和Ferry节点连通度的变化规律，在分析各因素相关性的基础上，采用逐步回归分析法得到区域连通度和Ferry节点连通度，并构建了网络连通性模型，仿真实验验证了该模型的合理性.
| [1] | 吴大鹏, 刘佳, 王汝言. 带有投递概率感知的低开销机会网络路由机制[J]. 北京邮电大学学报, 2013, 36(6): 64-68. Wu Dapeng, Liu Jia, Wang Ruyan. Cost-efficient routing mechanism with delivery probability perception in opportunistic networks[J]. Journal of Beijing University of Posts and Telecommunications, 2013, 36(6): 64-68.[引用本文:1] |
| [2] | Shu Jian, Zeng Linxin, Liu Linlan. Random graph model for opportunistic sensor networks based on divided area[C]//Advances in Wireless Sensor Networks. Berlin: Springer, 2014: 179-190.[引用本文:1] |
| [3] | Meghanathan N. Impact of the Gauss-Markov mobility model on network connectivity, lifetime and hop count of routes for mobile Ad hoc networks[J]. Journal of Networks, 2010, 5(5): 509-516.[引用本文:1] |
| [4] | Yang Peng, Freeman R A, Gordon G J, et al. Decentralized estimation and control of graph connectivity in mobile sensor networks[C]//American Control Conference. Seattle: IEEE, 2008: 2678-2683.[引用本文:1] |
| [5] | Ya AğG2 an O, Makowski A M. On the connectivity of sensor networks under random pairwise key predistribution[J]. IEEE Transactions on Information Theory, 2013, 59(9): 169-175.[引用本文:1] |
| [6] | Jin Wenlong, Recker W. An analytical model of multihop connectivity of inter-vehicle communication systems[J]. Wireless Communications, IEEE Transactions, 2010, 9(1): 106-112.[引用本文:1] |