间歇性分割的自组织网络路由算法和节点移动模型研究

在移动自组织网络的一些应用中，节点的快速移动等原因通常导致网络呈间歇性分割，此时常规的Ad hoc路由协议效率低下甚至无效，网络的可存活性面临着严峻的挑战。本项目研究间歇性分割的移动自组织网络的路由算法、节点移动模型及其相关理论。采用网络编码增加在冗余路径上的信息转发，提出具有抗毁能力的弹性路由算法；针对网络的间歇性分割问题，提出一种新颖的基于多维虚拟空间网格的网络拓扑分割检测算法和节点移动预测模型，为路由选择提供有效、合理的判据，提高间歇性分割的移动自组织网络的可存活性和抗毁能力；借鉴信息论的有噪信道模型和信道编码理论，研究拓扑快变且间歇性分割网络的路由技术，提出新的基于网络编码的不确定性路由转发的信道模型和理论，推动网络信息论的研究和发展。 2100433B

路由算法，又名选路算法，可以根据多个特性来加以区分。算法的目的是找到一条从源路由器到目的路由器的“好”路径（即具有最低费用的路径） 。算法设计者的特定目标影响了该路由协议的操作；具体来说存在着多种路由算法，每种算法对网络和路由器资源的影响都不同；由于路由算法使用多种度量标准（metric），从而影响到最佳路径的计算。路由算法通常具有下列设计目标的一个或多个：优化、简单、低耗、健壮、稳定、快速聚合、灵活性。（1）最优化：指路由算法选择最佳路径的能力。根据metric的值和权值来计算。（2）简洁性：算法设计必须简洁。路由协议在网络中必须高效地提供其功能，尽量减少软件和应用的开销。这在当实现路由算法的软件必须运行在物理资源有限的计算机上时尤其重要。（3）坚固性：路由算法处于非正常或不可预料的环境时，如硬件故障、负载过高或操作失误时，都能正确运行。由于路由器分布在网络联接点上，所以在它们出故障时会产生严重后果。最好的路由器算法通常能经受时间的考验，并在各种网络环境下被证实是可靠的。（4）快速收敛：收敛是在最佳路径的判断上所有路由器达到一致的过程。当某个网络事件引起路由可用或不可用时，路由器就发出更新信息。路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径。收敛慢的路由算法会造成路径循环或网络中断。（5）灵活性：路由算法要求可以快速、准确地适应各种网络环境。例如，某个网段发生故障，路由算法要能很快发现故障，并为使用该网段的所有路由选择另一条最佳路径。2100433B

可以看到，在LS和DV算法中，每个路由器都需要保存其他路由器的一些信息。随着网络规模的扩大，网络中的路由器也将增加。因此，路由表的规模也将增大，从而使路由器不能有效地处理网络流量。使用分级路由可以解决这个问题。让使用DV算法来查找节点间的最佳路由。

在下述情形中，网络中的每个节点保存了一个有17个记录的路由表。在分级路由中，路由器被分成很多组，称为区域。每个路由器都只有自己所在区域路由器的信息，而没有其他区域路由器的信息。所以在其路由表中，路由器只需要存储其他每个区域的一条记录。在这个例子中，我们将网络分为5个区域。

如果A想发送分组数据包到在区域2中的一个路由器（D、E、F或G），它就将分组数据包先发送到B，依此类推。可以看到，在这种类型的路由中，可以对路由表进行概括，因此网络效率提高了。上面的例子描述了一个两级的分级路由。同样我们也可以采用三级或者四级的分级路由。

在一个三级的分级路由中，网络被分为很多簇。每个簇由很多个区域组成，每个区域包含很多个路由器。分级路由广泛应用于互联网路由中，并且使用了多种路由协议。

本课题以无线传感器网络的目标跟踪为背景，研究节能的目标跟踪协议和算法，解决目前目标跟踪协议存在通信量大、参与跟踪的节点数目多从而导致耗能多的问题。具体研究无线传感器网络目标跟踪机制，节点感应度计算模型，并研究基于节点感应度的目标定位与跟踪算法。 本项目提出了一种节点感应度计算模型，该模型主要利用传感器节点感应到的信号强度与离目标的距离互相关特性，即感应到的信号强度越大，则感应度值越高。感应度值将作为跟踪过程中节点是否参与跟踪的依据之一。提出了基于多边形的目标跟踪框架-FaceTrack,该跟踪框架包括目标在多边形区域之间的穿越过程中目标跟踪方法，节点唤醒与休眠时机、主跟踪节点的选择方法等。模拟结果表明，FaceTrack跟踪框架能有效定位目标所在多边形区域。为了提高跟踪精度，即实现目标在多边形内部动态移动的跟踪与定位，本项目以节点感应度模型为基础，提出了一种节点自主决策是否参与跟踪的目标跟踪算法（NS-ADTT），该算法基于定位边采用加权质心算法对目标位置进行估计，并且，节点可根据自身感应度值及局部网络情况自主决策是否参与当前跟踪。仿真结果表明，在目标跟踪过程中，该算法在保证一定跟踪精度的基础上减少了参与跟踪的节点数， 降低了网络能耗，有效地延长了网络生命周期。 本项目对其他跟踪模式进行了探索，基于拍卖的思想，提出了基于拍卖的目标跟踪算法Auction-Based Adaptive Sensor Activation Algorithm(简称AASA)。拍卖机制让预测区域内的节点通过竞争产生最适合参与目标跟踪的节点。拍卖过程充分考虑了节点的剩余能量以及节点到目标预测距离。模拟结果表明,算法AASA在保持可接受跟踪质量的前提下,能有效地解决能量消耗不平衡的问题。