无线移动自组网

1无线移动自组网1.概述自组织网络（adhocnetwork）是由一群兼具终端及路由功能的设备通过无线链路形成的多跳临时性自治系统。如果节点是可移动的，这样的网络称为移动自组织网络（mobileadhocnetworks，MANET）。由于节点的发射功率有限，距离较远的两个节点必须借助其它节点的转发才能进行通信，因此节点之间构成无线多跳链路。这种网络中不存在固定的基础设施，如路由器、无线基站等，每个节点都兼有路由器和终端两种功能。作为终端，节点可以运行各种面向用户的应用程序；作为路由器，节点需要为其它节点转发数据包。自组织网络不需要任何中心控制，网络可以自动检测和无缝集成新节点；反过来，当任何节点移出网络时，剩余节点也能自动重配置来适应新的场景。这种无设施的网络能够在没有或者是现有网络基础设施失效的情况下，提供终端之间的相互通信，因而在军事作战及应急救援等方面有重要应用。比如，战场上单兵作战的士兵之间可以通过移动自组网通信和共享信息，在灾难现场可以紧急建立移动自组网进行救灾指挥和协调。移动自组网既可以独立工作，也可以以末端子网的形式接入现有网络，如Internet网络和蜂窝移动通信网络。与有固定基础设施的传统通信网络相比，移动自组网具有以下严重问题：（1）带宽有限。大多数移动自组网使用不需要无线电许可的ISM（Industrial,ScientificandMedical）频带。受无线频谱带宽的限制，加上通信冲突、信号衰减、噪声和信道间干扰等因素的影响，无线链路的有效带宽很有限。（2）单向链路。由于传输功率等的差异，节点间可能形成单向链路。（3）拓扑变化。每个节点可以任意速度和方向运动，受发射天线类型、发送功率、信道间干扰、地形和天气等综合因素的影响，节点间的无线链路是时变的，节点也可能失效，这些因素使得移动自组网的拓扑结构是随时变化的，而且变化难以预测。现有路由协议（如距离矢量、链路状态）不适合动态拓扑，需要设计相适应的路由协议。（4）能量有限。为方便节点的移动，节点一般采用电池供电，节点的能量非常有限，这给协议及程序设计带来一定的困难。节省电源、延长工作时间成为首要考虑的问题。（5）安全性差。由于采用无线信道、有限电源、分布式控制等技术，移动自组网更加容易受到被动窃听、主动入侵、拒绝服务等网络攻击。移动自组网的主要研究问题包括MAC层协议、路由协议和网络安全等。路由和信道分配是移动自组网要解决的最基本问题，MAC协议要解决多信道接入、通信冲突以及协议的可扩展性等，路由协议面临的最大难题是因节点的移动和失效引起的网络拓扑变化导致网络路由很不稳定，频繁的路由重建和路由维护不仅造成传输延迟增加，也带来很高的开销。2.无线移动自组网路由协议尽管移动自组网有很大的吸引力，但移动自组网实现起来比固定网络困难。固定网络在两个方面利用了其静态的特性，（1）固定网络在节点间主动传播网络拓扑信息，每个节点可以使用较低代价的算法预先计算好该拓扑下的路由；（2）固定网络在节点地址中隐含了路由线索，因为一个大型网络的完整拓扑不可能全局地处理或传播。但这两种技术都不适合由移动节点组成的网络，因为节点移动使得拓扑信息失效，而永久性的节点地址无法包含动态的2位置信息。然而，以下拓扑假设对于采用射频通信的移动自组网是有用的：物理上靠近的节点在网络拓扑上也可能靠近。也就是说，物理上靠近的节点可以通过少数几跳的无线链路连接起来。移动自组网中的路由协议按照路由决策依据的信息分为基于拓扑的路由和基于地理位置的路由两大类。基于拓扑的信息收集节点间的连接关系和链路特性，并据此计算最佳路由，计算得到的路由保存在路由表中。基于地理位置的路由收集节点的地理位置坐标，并据此进行路由决策，可以实现无状态的、分布式的转发决策。基于拓扑的路由按照触发路由计算的条件分为先应式（表驱动）路由和反应式（需求驱动）路由。先应式路由协议试图维护最新的、到网络中所有节点的路由。每当节点发现拓扑改变，就将路由更新信息广播到网络中其它节点，每个节点更新路由表。反应式路由协议仅当源节点需要向目的节点发送数据时，才启动一个路由发现过程；路由建立起来之后由一个路由维护过程进行维护，直到目的节点不可达，或者源节点不再需要发送数据。2.1先应式路由协议DSDV（Destination-SequencedDistance-Vector）[1]是一个典型的先应式路由协议，采用经典的距离矢量路由算法。每个节点保存一个路由表，记录所有可达的目的地，以及到达这些目的地的最小跳数。为在拓扑结构动态变化的网络中保持路由表的一致性，DSDV采用两种路由更新触发机制：1）每个节点周期性地发送路由更新消息，2）当发现拓扑结构发生改变时立即发送更新消息。DSDV不要求移动节点之间存在某种形式的时间同步，也不要求移动节点的更新过程之间存在什么相位关系。（路由更新触发机制，异步更新）节点发送的每个路由更新消息包含一个消息序号，该序号由发送节点产生。与其它距离矢量路由算法类似，路由更新消息中包含节点发布的新路由，每一条路由包含以下信息：1）目的地址，2）到达目的地址的跳数，3）该条路由的目的序号。其中，路由的目的序号是DSDV协议新增的，该序号由目的节点生成，用于指示路由的新旧。在路由信息的传播过程中，路由序号被发送到所有节点，供节点决定怎么使用和更新路由。当节点接收到新的路由信息时，新的路由信息会与之前得到的路由信息进行比较，具有最新序号的路由被采用，较早序号的路由被丢弃，若序号相等则较小跳数的路由被采用。若路由更新消息中的路由被采纳，则被采纳路由的跳数均加1，然后在下一次路由更新中发送出去。（路由更新信息，路由序号的生成和使用，路由更新）节点移动可能导致原先使用的链路中断。链路中断可被链路层检测到，或当节点长时间没有收到广播时推断出来。中断链路的跳数用∞表示，∞为任何大于最大跳数的数值。当节点检测到去往某个下一跳的链路中断时，将通过该下一跳的所有路由的跳数都标记为∞，并为这些路由分配新的序号。由于正常情况下路由的序号都由目的节点产生，只有表明中断链路的路由序号才由中间节点产生，为区分这两种情况，规定目的节点产生的序号为偶数，中间节点产生的序号为奇数。当节点收到一个∞跳数，随后又收到一个序号更高的、具有有限跳数的路由时，节点用“真实”的序号代替该路由，并触发一次路由更新广播，将该重要的信息传播到邻居节点。（链路中断的处理）当节点收到新的或变动较大的路由信息时，应当立即将这些信息广播出去，以使这些信息能够尽快传播到其它节点，加快路由的收敛。然而，当节点快速移动时，这会导致大量的广播，降低无线信道的可用性。为减少路由更新消息消耗的带宽，DSDV定义了两种类型的路由更新分组。一种称为fulldump（完全转存），携带完整的路由表；另一种称为incremental（增量更新），只携带上一次fulldump之后变化的路由信息。在设计上，一次增量路由更新3应当装入一个协议数据单元NPDU，完全转存可能会需要多个NPDU，即使在一个节点数较少的网络中。当节点移动较少较慢时，完全转存的发送频率可以低一些。当节点移动很频繁以致一次增量路由更新的数据量接近一个NPDU大小时，可以发送一个完全转存，这样下一次的增量分组就会小一些。协议假设节点能够判断哪些路由变化是重要的，从而应当触发一次增量更新，比如一条稳定路由的跳数发生改变时应当发送增量更新，而路由仅有序号变化、跳数不变，可以不发送增量更新。（完全转存和增量更新）由于节点会从多个邻居节点收到路由更新消息，各节点发送路由更新是异步的，新的路由又是根据路由序号和跳数来决定，因此很有可能会出现节点不断更新同一条路由（更新序号或更新跳数）的情况。如果每次变化都立即触发路由更新消息的发送，则会导致大量的广播发送，也会导致路由波动。事实上，节点几乎总是会收到序号不断增加的路由信息（最新序号总是从目的节点传播开来），并且较大跳数的路由总是最先到达。解决该问题的方法是，如果节点能够预测更好的路由即将到来，则推迟路由更新的发送，除非该路由的目的节点在此之前是不可达的。为此，每个节点需要有两个路由表，一个用于转发数据包，另外一个保存将通过增量更新分组发布的路由表。为了确定在发送路由更新前应等待多长时间，节点内部维护一张稳定时间表（settlingtimetable）。对于每一条路由，记录以下信息：1）目的地址，2）最近一次稳定时间，3）平均稳定时间，稳定时间为第一条路由到达和最佳路由到来之间的时间间隔。当一个路由更新到来时，如果新路由的序号比已有路由的序号新，但跳数大，则新路由被立即用来转发数据，但不立即发布，而是查询稳定时间表确定等待时间（如averagesettlingtime*2），待时间到后再发送路由更新。（确定路由更新消息的发送时机）举一个DSDV操作的例子。考虑图1中的MH4，表1是MH1离开MH2之前MH4的转发表。节点地址用MHi表示，序号用SNNN_MHi表示，其中MHi是生成该序号的节点，SNNN是序号值。Install域用于确定什么时候删除过时路由，ptrl_MHi为指向替换路由的指针。从表1可以看到，所有链路都是可用的，因为序号都为偶数。表2是MH4发布的路由表。图1网络拓扑表1MH4的转发表4表2MH4发布的路由表假设MH1离开MH2，进入MH5和MH7的邻域（即成为MH5和MH7的邻居）。MH5和MH7发现新邻居MH1后，立即触发一次增量路由更新，路由更新信息被广播给MH6。MH6判断这是一个重要的路由更新信息，也立即触发路由更新发送，将MH1的路由信息广播给MH4。收到路由更新消息后，MH4更新其转发表，表3是MH4的新转发表，其中表项MH1有跳数更新，其余表项有序号更新。MH4在随后的一系列增量路由更新中发送MH1的路由信息，直至发送fulldump为止。MH4发布的增量路由更新如表4所示，其中第一项是MH4，因为MH4是发布者，然后是MH1，因为MH1有重要路由更新。按照规定，跳数改变的路由要放在增量更新分组的前面。表3MH4的新转发表表4MH4发布的新路由表在移动自组网环境中使用分布式距离矢量路由算法的主要顾虑是容易形成路由环路和计数到无穷问题。形成路由环路的主要原因是各节点之间没有协同好，各节点可能会使用到一些错误的信息来更新各自的路由表，已有距离矢量路由算法都没有解决好这个问题，或者无法避免环路（如RIP），或者需要节点间复杂的协同而不具有实用性。DSDV使用序号解决了节点间的协同问题：1）每个节点总是使用最新最好的路由，避免路由环路的发生；2）使用奇数序号表示链路中断，避免了计数至无穷的问题。DSDV使用增量路由更新和稳定时5间表，大大减少了路由信令的开销。DSDV较适用于小规模的移动自组网网络，因为频繁的广播导致其控制消息的开销高达O(n2)，限制了网络的规模。其次，每个节点需要维护大量当前不活跃的路由，浪费了不少资源。2.2反应式路由协议AODV（Ad-hocOn-DemandDistanceVectorRouting）[2]协议是一个典型的反应式路由协议，仅当源节点希望向某个目的节点发送数据却并没有去往该目的节点的路由时，才启动路由发现过程。不在活跃路径上的节点不维护任何路由信息，也不参与任何周期性的路由表交换。AODV采用广播路由发现机制，依靠中间节点动态建立路由表，借鉴DSDV中目的节点序号的概念来维护最新的路由信息。（1）路由发现（pathdiscovery）当一个节点希望和另一个节点通信，但当前路由表中并无该节点的路由信息时，启动路由发现过程。每个节点维护两个独立的计数器：节点序号和广播ID。源节点通过向其邻居广播一个路由请求消息RREQ启动路由发现过程。RREQ消息包含源地址，源序号，广播ID，目的地址，目的序号，跳数这6个域，其中源地址，广播ID二元组唯一标识一个RREQ，每当源节点发送一个新的RREQ时要递增广播ID。邻居节点收到RREQ消息后，有三种可能：1）RREQ消息的源地址和广播ID与以前收到的某个RREQ相同（该RREQ消息