自组织网络及其路由技术
一、背景及概念
1.发展历史
无线通信网一般都是有中心的，要基于预设的网络基础架构才能运行。例如，蜂窝移动通信系统要有基站的支持；无线局域网一般也工作在有接入点（AP）和有线骨干网的模式下。但对于有些特殊场合来说，有中心的移动网络并不能胜任。比如，战场上部队快速展开和推进，地震或水灾后的营救等。这些场合的通信不能依赖于任何预设的网络设施，而需要一种能够临时快速自动组网的移动网络。无线自组织网络即可以满足这样的应用。
自组织网络技术的研究始于 20 世纪 70 年代。美国 DARPA 出于军事需要，开始研究分组无线网（PRNET）在战场环境下数据通信中的应用。项目完成之后，DAPRA 又在 1993 年启动了高残存性自适应网络项目。研究如何将 PRNET的成果加以扩展，以支持更大规模的网络，还要开发能够适应战场快速变化环境下的自适应网络协议。1994 年， DARPA 又启动了全球移动信息系统项目。在分组无线网已有成果的基础上对能够满足军事应用需要的、可快速展开、高抗毁性的移动信息系统进行全面深入的研究，并一直持续至今。1991 年成立的 IEEE 802.11 标准委员会采用了“无线自组织网络”一词描述这种特殊的对等式无线移动网络。
美国《福布斯》杂志报道了加州大学洛杉矶分校的无线传感器网络的研究项目，指出通过无线传感器网络，我们将实实在在地掌握这个物理世界。2003年美国《商业周刊》将无线传感器网络列为21世纪改变世界的10大技术之一。美国《技术评论》杂志评出对世界产生深远影响的十大新兴技术，无线传感器网络排名第一。另外，像 IEEE((ComPuter》等众多杂志也都发表了一些关于无限传感器网络的论文。我国也非常重视无线传感器网络的研究，中国国家自然科学基金委员会在2003年已经开始对无线传感器网络的研究进行了资助，并于2004年将其列为重点项目。2005年我国开始传感网络标准化研究工作。2006年，国家973计划，国家863高技术计划等国家和省部级科技发展“十一五”规划也设专项资助该领域的理论、方法和关键技术研究。
同年，我国政府将发展无线传感器网络列入未来15年的《国家中长期科学
和技术发展规划纲要(2006一2020年)》。2008年9月启动的国家16个重大专项中03专项设立7个方向，无线传感器网络为第6个一“短距离无线互联与传感器网络研发”。未来科学家预言无线传感器将引发新的信息革命，一些专家将传感器网络、塑料电子学和仿生人体器官并称为全球未来的三大高科技产业，它们将掀起新的产业浪潮。这些都预示着未来到处是以电池为能源的无线传感器网络，这些传感器可监控环境、机器甚至人类自己。
在自组织网络中，节点具有报文转发能力，节点间的通信可能要经过多个中间节点的转发，即经过多跳，这是自组织网络与其它移动网络的最根本区别。节点通过分层的网络协议和分布式算法相互协调，实现了网络的自动组织和运行。
2.自组织网络特点
无线自组织网络具有无中心和自组织性。网络中没有绝对的控制中心，所有节点的地位平等，网络中的节点通过分布式算法来协调彼此的行为，无需人工干预和任何其它预置的网络设施，可以在任何时刻任何地方快速展开并自动组网。由于网络的分布式特征、节点的冗余性和不存在单点故障点，使得网络的健壮性和抗毁性很好。所以与传统网络相比，无线自组织网络有以下特性：
1.自动配置：自动配置是无线自组织网络的一个特征，节点必须检测其它节点以及它们可以提供的服务。由于网络动态变化，自动配置过程需要确保网络能够正常工作，这涉及到连接 Internet 的网关节点的更换，簇头的更新等。在网络形成阶段，节点可以就网络拓扑进行协商（星形、环形、点到点、点到多点、平面和分级），这依赖于网络的类型、底层的无线技术和应用的需求。
2 .多跳性:由于节点发射功率的限制，其通信围有限。当它要与其通信围之外的节点进行通信时，需要中间节点的转发。另外， Adhoc网络中的多跳是由普通节点协作完成的，而不需要专用的路由设备(如路由器)来完成。
3.无中心和自组织性 :网络中没有绝对的控制中心，所有节点的地位平等，网络中的节点通过分布式算法来协调彼此的行为自组成网，无需人工干预和任何其它预置的网络设施。由于网络的分布式特征、节点的冗余性和不存在单点故障点，使得网络的健壮性和抗毁性很好。
4.动态拓扑 :网络中，移动终端能够以较随意的速度和方式移动，并可以随时关闭电台，加上无线发送装置的天线类型多种多样、发送功率的变化、无线信道间的互相干扰、地形和天气等综合因素的影响，移动终端间通过无线信道形成的网络拓扑可能随时发生变化，而且变化的方式和趋势都难以预测。
5.带宽的限制 :自组织网络采用无线传输技术作为底层通信手段，由于无线信道本身的物理特性，它所能提供的网络带宽相对有线信道要低得多。此外，同时无线自组织网络受限于无线传输带宽，由于采用无线传输技术作为底层通信手段，它所能提供的网络带宽相对有线信道要低得多。此外考虑到竞争共享无线信道产生的冲突、信号衰减、噪音和信道之间干扰等多种因素，移动终端得到的实际带宽远远小于理论上的最大带宽。
6.移动终端的局限性 :自组织网络中的移动终端具有携带方便、轻便灵巧等好处，但是也存在固有缺陷，例如能量有限、存较小、CPU性能较低等，从而给应用程序设计开发带来一定的难度，同时屏幕等外设较小，不利于开展功能较复杂的业务。
7.存在单向信道 :自组织网络采用无线信道通信，由于地形环境或发射功率等因素影响，一对节点之间可能产生单向信道。
8.安全性较差 :自组织网络是一种特殊的无线移动网络，由于采用无线信道、无中心、分布式控制和临时组织等技术，它更加容易受到被动窃听、主动入侵、拒绝服务、剥夺“睡眠”等网络攻击。信道加密、抗干扰、用户认证和其它安全措施都需要特别考虑。
3.Ad-hoc网络
AdHoc网络是目前讨论的最多的自组织网技术。这种网络不需要固定的基站设备和路由器，应此不依赖于蜂窝移动通信网络。网络中的节点可在一定区域随意移动并能于网络中的任意站点相互通信。每一个节点都能实现路由器的功能而在网络中搜寻、维护到另一节点的路由。自组织网可用在事故的突发现场以及人们希望能迅速共享信息的会议、办公室等场所。
AdHoc网络根据站点间的逻辑关系可以分为两种网络结构:平面网络结构、分级网络结构。如图1-1所示，左边的自组织网络是一个平面结构的网络，而右边的则是一个二级结构的自组织网络。平面结构中，所有节点地位平等，也被称为是对等式结构。与之相对的分级结构中，网络被划分为多个簇(cluster)，每个簇由一个簇首(cluster一header)和多个簇成员(cluster一member)组成。这些簇首
在逻辑上组成了一个高一级的网络，而在这个高一级的网络中又可以分簇，形成更高一级的网络，直至最高级。任意两个不在一个簇之的簇成员之间的通信都要通过各自的簇首来中转。
图1.1 平面结构VS分级结构
平面结构的自组织网络结构简单，由于站点间是对等一的逻辑关系无需任何的结构维护过程。源节点和目的节点之间可以存在多条路径，当一条路径繁忙时，可能通过另一条路径继续通信。由于网络中所有节点是对等的，原则上不存在瓶颈，所以比较健壮。平面结构的最大缺点是网络规模受限。在平面结构中，每一个节点都需要知道到达其它所有节点的路由。由于节点的移动性，维护这些动态变化的路由信息需要大量的控制消息。网络规模越大，路由维护的开销就越大。当网络的规模增加到某个程度时，所有的带宽都可能会被路由协议消耗掉。所以平面式结构网络的可扩展性较差。
分级结构的最大优点则是可以有效控制路由信息量的膨胀，可以支持更大的网络的规模，必要的时候可以通过增加新的簇或者增加网络级数来提高整个网络的容量。分级结构中，簇成员只需要维护簇站点间的路由信息，与簇外站点的通信交给簇首处理。即简化了成员站点的功能，又使得簇的网络管理信息量大大减少，节省了网络开销。簇成员无须知道其他簇的拓扑结构，一个簇的拓
扑变化不会被其它簇的节点感知，这就大大减少了网络中路由信息对无线链路带宽的消耗。簇首的功能较为复杂一些，不仅需要维护到达其他簇的路由信息，还要知道所有节点与簇的关系。网络中主要的路由功能由簇首完成，大部分路由、管理信息在由簇首组成的高级网络中传播。一般情况下簇首只是网络中的少数站点，在同样规模网络的条件下分级结构的路由开销要比平面结构的小。如果簇通信的信息流量在整个网络的通信量中占较大比例的时候，更能够明显提高整个网络的吞吐量。当然分级结构也有其缺点存在。首先维护不同层次结构间站点的逻辑关系较为复杂。簇首站点如果由事先指定，在站点移动情况下无法保证各个簇的规模相当;选举产生簇首的算法又较为复杂，需要仔细设计。其次簇的节点与簇外的节点进行通信时必须经过簇头，所得到的路由不一定是最佳路由。
第三簇首的通信负担较重，容易成为网络中的通信瓶颈。
从上面的比较可以看出，平面结构和分级结构的自组织网络各自具有不同的
优势。平面结构的自组织网络结构简单，站点间的路由较为灵活，不容易出现网络瓶颈。但是，在网络规模较大时路由更新信息的负载较重造成通信容量的下降。平面结构更适合较小规模的网络。分级结构通过路由信息局部化减小路由控制报文的开销，提高了系统的吞吐量;通过增加新的簇分级结构可以支持更大的网络规模，有较好的可扩展性;另外分级结构可通过簇首的管理功能为网络提供用户接入控制和站点定位等辅助功能。
在AdHoc网络当中，无论采用平面结构还是分级结构有一点是共同的:所有站点共享一个物理信道。分级结构网络虽然能够限制簇部的路由信息向其它簇扩散，但是分簇和分级都只是限于站点间逻辑关系而言，并不能隔离站点对物理信道的竞争。当网络中有站点数量越大，站点取得信道资源就越困难，出现信道冲突的可能性也相应增加。由于站点的通信距离限制，多数情况下AdHoc 。网络中存在多跳路径。多跳网络中隐藏终端的存在使得站点难以区分无线信道是空闲还是正被一个隐藏终端使用，物理信道冲突比有线以太网和单跳无线网络中更复杂。
4.无线传感自组织网的应用
无线自组织网络的许多优良特性为它在民用和军事通信领域占据一席之地
提供了有利的依据。首先，网络的自组织性提供了廉价而且快速部署网络的可能。其次，多跳和中间节点的转发特性可以在不降低网络覆盖围的条件下减少每个终端的发射围，从而降低设计天线和相关发射（接收）部件的难度，也降低了设备的功耗，从而为移动终端的小型化、低功耗提供了可能。从共享无线信道的角度来看，自组织网络降低了信号冲突的几率，提高了信道利用率。从对使用者的保护来看，高功率的无线电波产生的电磁辐射对用户的身体健康也有影响。另外，网络的鲁棒性、抗毁性满足了某些特定应用需求。它的应用场合可以分为以下几类：
1.紧急场合：在发生了地震、水灾、强热带风暴或遭受其它灾难打击后，固定的通信网络设施（如有线通信网络、蜂窝移动通信网络的基站等网络设施、卫星通信地球站以及微波接力站等）可能被全部摧毁或无法正常工作，对于抢险救灾来说，这时就需要无线自组织网络这种不依赖任何固定网络设施又能快速布设的自组织网络技术。类似地，处于边远或偏僻野外地区时，同样无法依赖固定或预设的网络设施进行通信。无线自组织网络技术的独立组网能力和自组织特点，是这些场合通信的最佳选择。
2.军事应用：军事应用是无线自组织网络技术的主要应用领域。因其特有的无需架设网络设施、可快速展开、抗毁性强等特点，它是数字化战场通信的首选技术。无线自组织网络技术已经成为美军战术互联网的核心技术。美军的近期数字电台和无线互联网控制器等主要通信装备都使用了自组织网络技术。
3.个人通信：个人局域网是无线自组织网络技术的另一应用领域。不仅可用于实现 PDA、手机、手提电脑等个人电子通信设备之间的通信，还可用于个人局域网之间的多跳通信。
4.传感器网络：传感器网络是无线自组织网络技术的另一大应用领域。对于很多应用场合来说传感器网络只能使用无线通信技术。而考虑到体积和节能等因素，传感器的发射功率不可能很大。使用无线自组织网络实现多跳通信是非常实用的解决方法。分散在各处的传感器组成无线自组织网络，可以实现传感器之间和与控制中心之间的通信。这在爆炸残留物检测等领域具有非常广阔的应用前景。
5.移动通信系统补充：无线自组织网络还可以与蜂窝移动通信系统相结合利用移动台的多跳转发能力扩大蜂窝移动通信系统的覆盖围、均衡相邻小区的业务、提高小区边缘的数据速率等。
6.商业应用：组建家庭无线网络、无线数据网络、移动医疗监护系统和无线设备网络，开展移动和可携带计算以及无所不在的通信业务等。
7.其它应用:考虑到Adhoc网络具有很多优良特性，它的应用领域还有很多，这需要我们进一步去挖掘。比如它可以用来扩展现有蜂窝移动通信系统的覆盖围，实现地铁和隧道等场合的无线覆盖，实现汽车和飞机等交通工具之间的通信，用于辅助教学和构建未来的移动无线城域网和自组织广域网等。
二、自组织网络的路由技术
1.路由算法设计目标
路由协议是ad-hoc网络的核心，是节点之间进行通信而采用的协议，主要由路由算法实现。由于网络中节点的移动性，网络拓扑的结构可能发生改变，因此路由算法要能满足动态路由的要求。选择和设计一个高效的路由算法对于一个ad-hoc网络来说显得非常重要，路由算法的好坏直接影响到ad-hoc网络的性能。Ad-hoc路由算法设计的首要问题是要求简单、高效并且控制开销小。本章主要研究ad-hoc路由算法的设计。