2. 中国科学院 电子学研究所, 北京 100190
针对如何指导路由节点移动这个问题，提出了一种新颖的路由节点移动决策机制。该机制包括移动路由节点分类、路由节点的状态转换、路由节点的移动决策、拓扑结构的优化。仿真结果表明，采用该机制的无线移动Mesh网络能阻止网络的分裂，为移动终端节点提供较高的转发吞吐量。
2. Institute of Electronics, Chinese Academy of Sciences University of Chinese Academy of Sciences Beijing, Beijing 100190, China
In response to the problem of how to guide the router nodes to move, a novel router node decision-making mechanism was proposed. This mechanism includes the classification of mobile router nodes, the state transition of router nodes, the movement decision of router nodes, and the topology optimization. The simulation results show that the wireless mobile Mesh network using this mechanism can prevent the network partitioning and provide higher forwarding throughput for the mobile client nodes.
无线移动Mesh网络(WM2N，wireless mobile mesh network)具有自组织、自配置、易扩展、多跳、低维护成本的特点，因此适用于可靠的有线通信设施损坏或无法提前部署的场景，如军事作战、应急通信和灾难救援等[1-2].目前，面向WM2N的跨层设计、路由技术、安全等领域已出现了一些有价值的研究成果，但迄今为止面向WM2N的拓扑控制技术还缺乏深入研究.如何设计路由节点移动决策机制以指导路由节点移动是一个具有挑战性的问题.
1 相关研究目前，在移动Ad hoc网络(MANET，mobile Ad hoc network)、无线传感器网络(WSN，wireless sensor network)和静态无线Mesh网络(SWMN，stationary wireless mesh network)的拓扑控制领域[1-3]，取得了较多的研究成果，且WM2N与MANET、WSN与SWMN之间，也具有一些相似之处.然而，已有的拓扑控制算法或协议却难以直接应用于WM2N中.下面将一一进行阐述.与MANET、WSN相比，WM2N中的拓扑控制技术主要存在以下不同：1)路由节点的移动目的不同.WM2N虽然组成骨干网的路由节点具有移动性，但路由节点的移动主要是支持移动的终端节点连接到骨干网，为它们提供Internet宽带接入.而MANET中的节点移动目的取决于移动实体的活动行为，类似于WM2N的终端节点，不同于路由节点.对于常规的WSN来说，其组成节点一般假设都是静止的.2)拓扑控制方法有明显区别.WM2N的路由节点与MANET、WSN的节点相比，WM2N的路由节点具有更强大的通信能力，路由节点在进行拓扑控制时，除常规的功率控制、覆盖调度等调控手段外，还有信道分配、调整有向天线角度等手段来优化网络的拓扑结构.3)评价机制迥异.如拿“覆盖”指标来说，MANET一般没有该评价指标.WSN的拓扑控制技术大多数倾向于覆盖全部的“兴趣”监测区域或监测点，而WM2N覆盖实现的是终端节点能与路由节点或其他终端节点Mesh相连，建立到骨干网的传输路径.
现有的SWMN中拓扑控制领域的协议或算法难以适应于WM2N，主要原因为：1)现有算法难以适用于骨干网物理拓扑结构动态变化的情况.2)缺乏指导路由节点移动的相关方法.如之前所述，路由节点的移动能力虽可拓宽WM2N的应用环境和应用领域，但却大大增加了拓扑控制问题的复杂性：1)在终端节点移动过程中，在确保终端节点可连接到骨干网并保证骨干网连通性的前提下，如何设计路由节点移动决策机制，以指导路由节点移动是一个具有挑战性的问题.2)标准无线Mesh网络一旦部署，骨干网的物理拓扑结构已经固定，优化网络的逻辑拓扑结构可采用集中式方法，而移动Mesh骨干网中路由节点的位置受终端节点的影响，经常变化且无法预知，导致拓扑控制技术只能采用分布式的求解方案，这也增加问题的难度.3)此外，在WM2N中，考虑到终端节点有限计算能力、电池资源、部署位置频繁变化等特点，为保证终端节点能可靠连通到骨干网，形成骨干网与终端节点间的逻辑拓扑结构，只能采用轻量级的、快速有效的解决方案.但迄今为止，WM2N研究中还鲜有研究涉及骨干网与终端节点间的逻辑拓扑结构构造技术.笔者提出了一种新颖的面向无线移动Mesh网络的路由节点移动决策机制，指导路由节点的移动，动态地调整拓扑结构，以支持移动终端节点连接到骨干网.
2 路由节点移动决策机制初始配置1个由Mesh路由节点组成的连通的多跳骨干网络.假设每个Mesh路由节点配备1个定位装置，如全球定位系统(GPS，global positioning system).终端节点随机部署在骨干网的覆盖范围，每个终端节点至少与1个Mesh路由节点连接.笔者不讨论孤立终端节点存在的场景，只考虑终端节点在初始配置时全覆盖的场景.每个终端节点可组成1个组，属于同一个群组的Mesh终端节点具有相似的运动特征.不同组的终端节点可遵循不同的群组移动模型，如参考点群组移动模型、基于引力和斥力的群组移动模型、自回归群组移动模型等，运动到不同的方向[7].笔者的目标是采用路由节点移动决策机制指导路由节点移动，支持移动终端节点连接到骨干网.
2.1 移动Mesh路由节点分类为了支持动态变化的Mesh拓扑结构，移动Mesh路由节点根据它们当前的角色分为以下类型：
1)群组内部路由节点.如果Mesh路由节点的通信范围内至少存在1个终端节点，则该Mesh路由节点叫作群组内部路由节点.组内的Mesh终端通过该路由节点与其他终端进行通信.
2)桥接路由节点.如果Mesh路由节点不覆盖任意终端节点，起到中继节点的角色，帮助群组与骨干网连接，支持移动终端节点连接到骨干网，则该Mesh路由节点叫做桥接路由节点.对于每个群组，指派至少1个桥接路由节点负责群组的内部路由节点与骨干网或其他群组进行通信，如图 1所示的群组G1中路由节点B1.
|
图 1 骨干网和群组G1 |
3)空闲路由节点.如果Mesh路由节点既不是群组内部路由节点，也不是桥接路由节点，则该Mesh路由节点叫做空闲路由节点.
笔者假设有足够多的空闲路由节点散布在骨干网周围.每个Mesh路由节点在初始位置都充满电，有足够的能力更新它们的位置信息，为终端节点转发数据.然而，一旦组内或桥接路由节点监测其自身的能量级别较低时，它将申请用1个空闲路由节点替代它.被替代的路由节点将申明成为空闲路由节点并返回初始位置，如控制中心、替换电池.以上策略阻止路由节点因能量耗尽而导致网络的分裂.
为了追踪移动终端节点，笔者与Elmano等[4-6]提出的策略不同，不需要通过群组内部路由节点来跟踪终端节点，当终端节点没有接收到骨干网中任意路由节点广播的信标信息，则将停顿片刻，触发邻居空闲路由节点跟随它，当收到邻居空闲路由节点的确认信息后，该终端节点继续运动，以确保该路由节点为其提供连接骨干网的支持.
2.2 移动Mesh路由节点的节点类型转换算法1描述了路由节点r的节点类型转换，处于不同类型的路由节点在不同的转换条件下将改变其节点类型.
算法1 路由节点r的节点类型转换
1 每隔信标时间间隔
2 switch路由节点r的节点类型do
3 Case Intragroup
4 如果不覆盖任意终端节点
5 switch to the Bridge
6 否则不需采取任何措施
7 Case Bridge
8 如果有新增的终端节点
9 switch to the Intragroup
10 否则将自己的位置信息加载到转发的数据包中，以备将来收回使用
11 Case Free
12 如果接收到终端节点发送的请求跟踪信息
13 则定位到该终端节点，发送确认信息给该终端节点
14 switch to the Intragroup
15 请求一些空闲路由节点跟随该新的intragroup router
16 结束
2.3 路由节点移动决策机制路由节点移动决策机制分为跟随终端节点移动、收回多余的路由节点、连接分离的群组与骨干网，下面将详细叙述.
2.3.1 跟随终端节点移动当终端节点不再收到任何路由节点发出的信标信息，则说明该终端节点不被任何路由节点所覆盖.如图 2(a)所示，终端节点TN2不再收到路由节点R7的信标信息，则暗示TN2移出路由节点R7的覆盖范围，由于TN2收不到其他任意路由节点的信标信息，则说明TN2进入不被群组内任何路由节点覆盖的区域，这时群组拓扑结构需要调整来扩展新的覆盖范围以包含TN2的新位置.为了完成这个目标，一旦终端节点不再收到期望的任意路由节点的信标信息，则它将停顿片刻，发送相关信息来触发邻居空闲路由节点来跟随该终端节点.在图 2(b)中，当空闲路由节点F1收到TN2的请求跟随信息，则F1将先定位到终端节点TN2，然后发确认信息给TN2，并改变操作模式，变成新的群组内路由节点.新的群组内路由节点F1与余下的群组内路由节点R7是连通的，因为它在路由节点R7的覆盖范围内.当TN2收到跟随确认信息后，继续移动.
|
图 2 群组拓扑结构的变化过程 |
依据终端节点的移动，组内和桥接路由节点不再需要时，收回这些节点以备将来使用.在此仅讨论组内路由节点的情况，桥接路由节点将在下面小节作讲述.如图 3(a)所示，在路由节点R5的覆盖范围内，不存在任意终端节点，这时路由节点R5将通过以下步骤改变操作模式：路由节点R5如果接收不到任意终端节点的Hello信息，则发送1条消息通知它的邻居路由节点它将改变操作模式的意向，当收到所有邻居路由节点的确认信息后，R5将改变成桥接路由节点.这个过程有3点需要注意：第一，应该避免多个组内路由节点同时改变操作模式，将导致某些终端节点不被路由节点覆盖；第二，冗余的组内路由节点只能先请求将自己的操作模式变为桥接路由节点，而不是空闲节点，因为它可能连接分离的群组与骨干网；第三，生成多余的桥接路由节点，当空闲路由节点缺少时，这些节点可回收变成空闲节点，在下面小节中给予说明.
|
图 3 骨干网的拓扑结构动态变化过程 |
初始配置时，所有终端节点是被骨干网覆盖的，当这些终端节点移出骨干网的覆盖区域分离成不同的小组.为了避免网络分裂，某些空闲路由节点将改变其操作模式成为每个组内路由节点；当组内路由节点的覆盖范围内不存在终端节点时，则组内路由节点将改变其操作模式成为桥接路由节点，帮助连接群组与骨干网，让它们之间保持通信.
3 拓扑结构优化到目前为止，讨论的机制主要是确保Mesh路由节点维持所有终端用户的连通性.余下的网络，随着多余的不必要的桥接路由节点的增加，端对端的延迟将增加.为了改进这种情形，笔者提出了一种拓扑结构优化机制来缩短群组之间的路由路径.笔者将直接与群组内部路由节点相连的桥接路由节点叫做I类桥接路由节点，如图 3(b)所示的B1、B2、B3、B4、B5和B6，其余桥接路由节点为Ⅱ类桥接路由节点.
如图 3(b)所示，为了节约Ⅱ类桥接路由节点，用星型网络代替桥接网络.星型拓扑结构通常提供更短的路由路径.执行拓扑结构的优化分为2种情况：
1)当Ⅰ类桥接路由节点监测到大于1个桥接网络汇聚该点时，如图 3(b)所示的B6，它将作为协调者建立分配列表，如果该分配方案能节约更多的Ⅱ类桥接路由节点，则执行该拓扑优化过程，否则不执行该操作.在执行拓扑优化过程中，为了协调Ⅱ类桥接路由节点，借用3步握手协议.当协调者发送出它的安排列表给其Ⅱ类桥接路由节点后，它将等待这些路由节点的确认.如果所有的Ⅱ类桥接路由节点都同意参与，则协调器将发送1个通知给它们操作拓扑结构的调整，否则协调器将删除这次调整.如果Ⅱ类桥接路由器未被分配到新建的星型网络中，则将改变其操作模式成为空闲路由器，返回空闲池.
2)当Ⅰ类桥接路由节点(如B1)收集到本地位置信息后，它注意到其他Ⅰ类桥接路由节点B2与其所处的位置靠近.这说明相应的群组G1、G2在邻近区域.为了更加有效地连接它们，B1扮演协调者来触发拓扑结构的调整.如果该分配方案能节约更多的Ⅱ类桥接路由节点，则执行该拓扑优化过程，否则不执行该操作.在执行拓扑优化过程中，B1针对B2和自身的位置决定星型拓扑结构的中心.
重复以上过程，直到拓扑结构无法再优化为止，如图 3(c)所示.
4 实验仿真笔者在NS2(network simulator version 2)中对上述路由节点移动决策机制进行了仿真，研究其在动态环境下的性能，比较以下3种方案.
1)采用基于Delaunay三角剖分的拓扑结构作为WM2N的拓扑结构，通过路由节点移动决策机制跟随任意被选择的终端节点，为移动的终端节点提供连接支持.该网络始终维持Delaunay三角剖分的拓扑结构，简称Delaunay三角网格(DTM，delaunay triangle-based mesh).
2)采用路由节点移动决策机制的WM2N，如前面所述，动态调整拓扑结构，为移动终端提供连接骨干网络的支持，但不维持Delaunay三角剖分的拓扑结构，不进行拓扑结构的优化，简称基于网格的自适应拓扑控制方案(ATCM，adaptive topology control scheme-based mesh).
3)采用路由节点移动决策机制并能优化网络拓扑结构的WM2N，简称基于网格的自适应拓扑控制和减少方案(ATCRM，adaptive topology control and reduce scheme-based mesh).
除了以上叙述，笔者采用以下默认的参数值.初始部署多跳的骨干网，覆盖所有的终端节点.Mesh路由节点的通信半径为150 m，路由协议采用AODV协议.终端节点的最大移动速度为3 m/s，Mesh路由节点的最大移动速度为15 m/s.每次仿真时间为900 s.数据流类型为恒定比特率(CBR，constant byte rate)，每个发送节点每隔0.005 s发送1个报文，报文长度固定为1 KB.发送率为1 MB/s.笔者的仿真结果记录是取30次仿真数据的平均值.
1)终端节点移出骨干网的距离对所需路由节点数目的影响
当终端节点移出骨干网的初始覆盖范围时，随着距离的增加，所需的路由节点增多.图 4显示1个群组移出骨干网的初始覆盖范围，移出骨干网的距离从0~2 500 m，所需的平均路由节点的数目，为其提供连接骨干网的支持(初始部署的骨干网中的路由节点不计算在内).ATCM、ATCRM所需的Mesh路由节点相同，因为只有1个群组移出骨干网，所以无法对网络拓扑结构进行优化.DTM比ATCM、ATCRM需要更多的Mesh路由节点，比ATCRM、ATCM多出接近4倍的路由节点数目，因为DTM始终保持Delaunay三角剖分的拓扑结构.
|
图 4 终端节点移出骨干网的距离对所需路由节点数目的影响 |
2)提供全覆盖所需的Mesh路由节点数目
下面研究当终端节点移出骨干网的覆盖范围时，分离成不同的群组，需要提供多少数目的Mesh路由节点才能全覆盖所有的终端节点.假设有无限个Mesh路由节点.终端节点从30个增至150个，所有的终端节点移出骨干网的初始覆盖范围(部署初始骨干网所需的Mesh路由节点不计算在内)，移出骨干网的距离不超过2 500 m，分离成6个群组.图 5显示Mesh路由节点的平均数目被选作群组内部路由节点或桥接路由节点去覆盖所有的终端节点.DTM需要比ATCRM多出4倍的路由节点，因为DTM维持固定的拓扑结构，浪费了很多路由节点去覆盖无终端节点的区域.ATCM比ATCRM需要更多的路由节点，因为ATCM没有拓扑结构优化的机制.覆盖所有终端节点所需的移动Mesh路由节点的数目，不会随着终端节点的增加而增加.这暗示当移动终端节点分离成有限群组时，终端节点数目的增加不会引起ATCRM的扩展.这种结果是期望的，因为属于同一个群组的终端节点仅需要少数Mesh路由节点覆盖它们，帮助转发它们的数据.因此，ATCRM的扩展性仅受限于网络分裂的程度.当移动终端节点分离成很多不同的群组同时移向不同的方向占据整个应用地形时，将需要足够的路由节点维持分离群组与骨干网之间的连接.然而，在实际应用中，笔者考虑群组的数目相对于终端节点的数目很小的情况.所以，如果它们分离成少数群组，ATCRM能支持更多的移动终端节点.
|
图 5 覆盖移动终端节点所需的移动Mesh路由节点的数目 |
3)数据转发的性能
笔者将ATCRM与传统的移动Ad hoc网络比较.由于MANET不是基于基础设施的网络，因此在MANET中，每个终端节点可被看作是移动的路由节点，它们既能发送和转发自己的数据，也能为其他用户转发数据.仿真环境包括100个终端节点，它们将移出骨干网的覆盖范围，距离不超过2 500 m，分裂成6个群组.每个路由节点转发数据的发送率为1 Mbit/s.笔者将随意选择6对节点同时发送UDP流，每个数据流的发送率为1 MB/s.图 6显示随着路由节点的增加，所有数据流的平均吞吐量.ATCRM的平均吞吐量比DTM高出约60%，因为DTM中并非任意路由节点都参与数据的传送.ATCRM的平均吞吐量比ATCM高，因为ATCRM比ATCM具有更短的路由路径.而在Ad hoc中，由于节点的移动具有随意性，所以有可能造成网络的分裂，使其吞吐量为0.结果表明，在高度动态的应用场景，如军事作战、应急通信和灾难救援等，需要路由节点移动决策机制指导路由节点的移动，动态地调整拓扑结构，以支持移动终端节点连接到骨干网.
|
图 6 路由节点的数目对网络吞吐量的影响 |
由于特殊的应用领域，如科学考察、海洋探索、地质勘探、灾后救援和军事作战等，具有很多不确定性，所以无法提前部署昂贵的基础设施，使其完全覆盖终端节点，目前没有有效的方法解决该场景遇到的问题.笔者提出了一种分布式的路由节点移动决策机制，让空闲路由节点跟随移出骨干网覆盖范围的终端节点，动态地调整网络拓扑结构，为终端节点与骨干网之间提供无缝连接，阻止了因终端节点移动而造成与骨干网络的分裂.实验仿真证明，ATCRM使用最少的路由节点为移动终端与骨干网提供连接支持，当移动终端节点形成的群组个数越多，向不同的方向移动到不同的地形区域，则需要的路由节点越多.笔者讨论的是形成的群组个数很少的情况，相对于终端节点个数而言，这种假设更加接近实际，能运用到很多场景，但上述机制如何适应更大规模的网络结构，将进一步去探索研究.
| [1] | Akyildiz I F, Wang Xudong, Wang Weilin. Wireless mesh networks:a survey[J]. Computer Networks , 2005, 43 (9) :445–487. |
| [2] | Miyao K, Nakayama H, Ansari N, et al. LTRT:an efficient and reliable topology control algorithm for Ad hoc networks[J]. IEEE Transactions on Wireless Communications , 2009, 8 (12) :6050–6058. doi:10.1109/TWC.2009.12.090073 |
| [3] | Xu Hongli, Huang Liusheng, Liu Wang, et al. Topology control for delay-constraint data collection in wireless sensor networks[J]. Proceedings of Computer Communications , 2009 :1820–1828. |
| [4] | Elmano R C. On the interactions between mobility models and metrics in mobile Ad hoc networks[J]. International Journal of Networks and Communications , 2013, 3 (3) :63–80. |
| [5] | Shen Weiliang, Chen Chungshiuan. Autonomous mobile mesh networks[J]. IEEE Transaction on Mobile Computing , 2014, 13 (2) :364–376. doi:10.1109/TMC.2012.259 |
| [6] | Anand S, Eytan M. Joint node placement and assignment for throughput optimization in mobile backbone networks[J]. IEEE Journal on Selected Areas in Communications , 2012, 30 (5) :975–985. doi:10.1109/JSAC.2012.120612 |
| [7] | Andréa G R, Rute S. A survey on mobility models for wireless networks[R]. SITI Technical Report SITI-TR-11-01, February 2011. |