英文摘要:This paper examines network control processes and conflict in an Ad hoc network in ordinary mode and Mesh mode in Wide Area Network(WAN). Distributed network management is proposed with a back-off mechanism and algorithm. The process and performance of this algorithm is analyzed, and other key issues and trends in network management are discussed in conclusion.

英文关键字:network management; back-off algorithm; Ad hoc network; certification process

基金项目：国家高技术研究发展(“863”)计划(2008AA011004)

目前，公共安全机构和组织在应急处理和灾害响应时，越来越多地采用无线技术提供高效的命令、控制和通信保障。近年来多次紧急事件和灾害显示，出现紧急事件和发生灾害的时间、地点和规模难以预测。加之当有灾害事件发生时，既有的通信设施和手段往往遭到破坏，依赖既有的网络基础设施来进行应急通信的质量需求是无法保障的[1]。因此，具有分布式、移动性、扩充性、自适应性和灵活性的无线自组织网络成为进行应急通信组网的重要手段。

1 自组织应急通信网络概述

自组织(Ad hoc)网络是一种多跳的自治系统。1968年在美国建立的ALOHA网络和在1973年提出的PR网络就是自组织网络的原型。其实ALOHA是一种单跳网络，需要固定的基站，网络中的每个节点之间都可直接连接互相通信。而PR网络的提出，才是真正意义上地实现了多跳网络。PR网络中各节点无需直接连接，在两个距离远而无法直接通信的节点之间，能够通过中继的方式传送信息。PR网络之后改名为Ad hoc网络，即自组织网络。还有一些与Ad hoc网络技术相关的研究项目获得资助，包括可生存自适应网络(SURAN)、低成本报文无线电(LCR)、可生存通信网络(SCN)、战术因特网和近期无线电(NTDR)等[2]，这些网络的研究成果为自组织应急通信网络的研究奠定了重要的基础。

自组织应急通信网络是应用自组织网络技术构造满足应急通信需求的网络。自组织应急通信网指在紧急情况下不需要依靠既有的网络基础设施，利用具备自组织网络能力的通信节点，快速地组建通信网络，提供应急通信能力的网络。这个网络由一组带有无线收发装置的可移动节点组成无中心网络；是可以不依赖人为操作的自组织、自愈合的网络。网络中的各个节点相互协作，实现信息交换和服务共享。由于自组织应急通信网络独特的组网方式，网络具有6个显著特点：网络拓扑结构动态变化、自组织无中心、多跳通信、节点处理能力和能源受限、无线传输带宽受限、通信安全面临挑战[3]。

另一方面，自组织应急通信网络也具备了高可靠性、灵活性和低成本的特点；网络中多个通信路径和自动路径配置成为可能。网络中每个节点都兼有主机和路由器两种功能：作为主机节点运行各种用户程序，作为路由器节点运行网络配置的路由协议。在通信过程中，如果网络或环境发生变化，网络中的节点则协同工作，节点自动地重新配置，为所传递的信息寻找最合适的有效路径。因此，自组织应急通信网络重要的能力就是自动快速组网和通信。

第三代移动通信协作项目(3GPP)、欧洲通信标准化组织(ETSI)和互联网工程任务组(IETF)等标准化组织都在自组织应急通信网络方面展开了研究，并制订了相关的标准[4-5]。IETF专门设立了一个移动自组织网络研究课题组(MANET)，针对无线自组织多跳网络开发基于IP的路由协议，使IP协议扩展到自组织组网的无线网络；3GPP和IETF在自组织网络节点接入和自优化等方面制订了标准。它们的区别在于，3GPP规定标准的使用环境为全球无线接入网络(UTRAN)和演进通用陆地无线接入网络(E-UTRAN)，而ETSI标准适用环境为SP-42、SP-46。可以看到，关于自组织应急通信网络标准还没有制订出统一的、协调一致的标准。

本文为解决出现突发事件后无线自组织应急通信网络的快速组网问题，提出使用“时间关键”组网技术。“时间关键”源于军用战术通信网络中从发现目标、定位目标、直到攻击目标的时间限制要素。根据突发事件的等级，制订从网络建立需求提出，网络组建，网络节点入网和认证，网络通信启动，直至移动节点全部入网的时间限制。本文针对时间关键的入网过程中的机制、入网流程、入网协议和消息等方面，对这个过程中出现的节点冲突问题进行分析，提出相应的入网管理方法。

2 入网过程

入网过程是无线自组织网络组网的重要环节，节点入网可能在网络的初始化或新节点的加入两种情况发生。入网过程中入网流程和入网协议是两个重要的内容。为了满足“时间关键”组网的要求，首要的任务是标准化入网流程。下面通过一个新节点按照网络的特性，快速加入到网络中的控制过程，认识入网算法和管理功能。

2.1 标准入网流程

无线自组织网络中的节点入网流程是数据链路层的MAC子层的一个流程。在GSM、CDMA网络中规定了标准入网流程。在IEEE 802.16d[6]和MIL-STD-188-220[7]中，分别定义了Ad hoc模式下的入网流程。入网流程主要包括：网络同步、能力交换、认证注册等。各个无线自组织网络基本流程是相似的，因此参考IEEE 802.16d中的Mesh模式，本文定义并且描述了一个新节点在无线自组织应急通信网络中的入网流程。

2.2 入网协议和消息

在入网过程中新节点入网需要用到的两个消息：一个是MSH-NCFG，另一个是MSH-NENT。MSH-NCFG消息由网络中的节点发出，为相邻节点提供了基本的通信信息，在网络中的节点都应该按照一定方式转发MSH-NCFG消息。MSH-NENT消息是为新节点获取同步、进行实体初始化、加入网络提供方法的。

2.3 入网过程

入网流程主要包括网络同步、能力交换、认证注册等。每个无线Ad hoc网络的入网流程基本一致。

一个新节点来到网络时，首先通过监听到的邻居节点发送的MSH-NCFG消息来获得大致的网络同步及相关网络参数；该新节点根据随后监听到的邻居节点的MSH-NCFG消息建立一个物理邻居列表，此时完成了网络的大致同步；然后，该新节点依据“最易进行精确同步”的原则，从建立的物理邻居列表中选择一个合适的候选代理节点作为入网请求转发节点；该新节点通过竞争获得一个发送机会，向候选节点发送包含候选节点ID的入网请求消息(MSH-NENT)。

当候选节点收到请求消息时，判断是否接受这个请求。如果不接受，则回复MSH-NCFG: NetEntryReject消息；如果接受，则回复MSH-NCFG:NetEntryOpen消息，候选节点变为新节点的代理节点。新的代理节点所发送的MSH-NCFG:NetEntryOpen中包含时延信息用以帮助新节点完成精确同步，并为新节点开放一个临时的通信调度支持资源。新节点利用代理提供的调度资源进一步执行能力交换、认证程序和注册程序。完成上述程序后，新节点通知代理；代理则释放临时调度支持资源，并给新节点发送确认消息。以后新节点就可在网络中正常工作。

上述过程参考了IEEE 802.16标准的入网流程，MIL-STD-188-220协议也规定了Ad hoc模式下的入网流程。IEEE 802.16WG下的标准IEEE 802.16e考虑了移动性管理[8]。TGm任务组已经发布了相应的需求文件SRD，在802.16m PAR中还明确了要满足IMT-Advanced需求。可以预期，IEEE 802.16m标准一旦完成，将对自组织应急通信网络的发展和研究起到很大的促进作用。

2.4 需要解决的问题

从无线自组织应急通信网络节点入网过程看，存在几个需要研究解决的问题。

(1)新节点为了加入到既有的网络中，首先要监听可以收到的相邻节点的网络配置消息。而结束这个监听过程的条件是重复收到从一个相邻节点发来的网络配置消息。由此，结束这个监听过程取决于可能的相邻节点重复发送网络配置消息的间隔时间。

(2)新节点在选择候选担保节点时，选择最容易与新节点进行精确同步的节点。这仅仅考虑了物理时间同步关系，没有对节点的通信能力给与足够的考虑。

(3)IEEE 802.16d的Mesh网络，存在着基站设备。新节点通信能力、认证程序和注册程序都通过基站完成。MIL-STD-188-220B/C/D标准中定义了入网过程，但是某些无线自组织网络种中没有给出节点入网过程的描述。在没有基础网络结构的无线自组织应急通信网络中，由于新节点能力很不同，认证过程和注册程序应该有所不同。

(4)在新节点入网检测的过程中，引入认知无线网络技术，对新节点感知相邻节点、选择担保节点、选择信息交换时机，以及认证和注册过程都可以产生影响。

3 入网管理

依据上述自组织应急通信网络节点入网过程，一个新节点加入网络需要占用3个网络接入时机发送MSH-NENT消息，而候选/代理节点则需要占用3个网络配置时机发送MSH-NCFG消息来响应。

新节点占用网络接入时机是通过竞争的方式实现的。在IEEE 802.16协议中没有明确说明采用什么样的竞争方法。为保证候选/代理节点获得一个网络配置时机，在IEEE 802.16协议中给出了一个冲突避免的接入方法，该方法可以保证在网的节点发送MSH-NCFG消息时不会产生冲突。该方法的原理就是让所有成员节点考虑自己两跳以内节点的MSH-NCFG更新时间，选择出一个网络配置时机，使之不会跟两跳内所有节点有冲突，再发送自己的MSH-NCFG消息。

在入网流程中上述两个时机的占用方式，对不同场景下的新节点接入性能会有很大的影响。下面分两种场景来说明问题，一种是在普通模式下，即节点的通信范围都比较小的时候；另一种是在广域模式下，即节点的通信范围比较大的时候。本文通过对两种模式下的特性进行分析，得出入网管理方法。

 3.1 普通Mesh模式入网

虽然IEEE 802.16协议中没有特别规定Mesh模式下节点的通信范围，但是参照IEEE 802.16协议的PMP模式(小区模式)来估算，节点的覆盖范围为十几公里。这种场景下，网络的拓扑会比较复杂，跳数会增加。首先考虑以下情景，如图1所示。

假设节点A、B都为成员节点，即已加入了网络，并且A、B节点都不处于各自的通信范围内，而且彼此也不是对方的两跳邻居节点，因此节点A、B可以选择网络控制子帧的同一个网络配置时机来发送自己的MSH-NCFG消息，而彼此不会产生影响。这时一个新的节点C要加入网络，如图2所示。

由于节点C的到来，使得原来没有关系的节点A和B现在变成了两跳邻居。这时假设节点C在某个网络接入时机成功地向节点A发送MSH-NENT请求消息。节点A接受了这个请求消息后，在自己的网络配置时机发送MSH-NCFG消息进行应答。但是，由于节点B不知道节点A已经变成了两跳邻居，所以节点B也会在同一个网络配置时机发送自己的MSH-NCFG消息，这样节点C就不能正确地接收到节点A的应答，所以节点C在超时后会重发请求消息。在节点密度比较大的情况下，这种类型的冲突会很多，造成很大的网络接入延迟。这个问题的解决方法很重要，文献[9]中给出了一种方法。

3.2 广域Mesh模式入网

在广域模式下，节点的通信范围比较大，基本上不会产生普通Mesh模式下存在的问题，可是会带来新问题。新问题的描述如图3所示。

节点A是已有的网络成员，在某一时刻节点B和节点C同时到达网络并完成了网络信号同步。对3个节点而言，他们通信范围都比较大，都处在彼此的通信范围内。这时如果节点B和节点C同时向节点A发送入网请求MSH-NENT消息，则会导致冲突。尤其在大量节点要加入网络的时候，这种冲突会更加频繁，问题更加明显。

3.3 管理方法

由于无线自组织应急通信网络的应用场景就是要求节点快速进入网络，所以在网络节点入网发生冲突时，需要有效的冲突解决算法，以保障快速解决冲突，完成节点入网。

在用于竞争/冲突的网络资源管理中的应用中已经表明，退避算法是一种解决冲突的有效方法。针对自组织应急通信网络而言，如果在已知有大量入网的节点加入网络，并且已知这些节点信息的时候，选用集中式的静态配置的入网管理方法，将能够让所有节点以完全无冲突的、最小时延的方式迅速加入网络。只是这种方式的条件太过苛刻，因此本文提出大规模的节点分布式入网管理方法。

分布式入网的基本思想是基于窗口选择的退避机制，即给定一个随机窗口。在这个窗口中选择一个随机数，以这个随机数为基础，每当检测到网络的一个空闲时隙，则随机数值减1。当随机数减到0时，节点就认为这时可以发送。从这个过程中可以看到，如何选择随机窗口，如何在随机窗口中选择出一个随机数，当随机数减为0，进行发送时如何解决冲突是影响算法性能的几个重要因素。

在退避算法中，SW为选择窗口，WC为窗口计数器，RN为随机数字，FT为失败次数，ST为成功次数。文献[9-10]对算法性能进行了分析。

假设初始节点总数为N，窗口的选择系数为x，则窗口的长度L=xN，在xN长度内N个节点采用均匀随机过程接入，产生冲突的概率记为函数：Pc(x)=冲突的次数/窗口总数。在xN长度内N个节点采用均匀随机分布过程接入，成功传递的概率记为函数：Ps(x)=成功传送次数/传送总次数。设时隙长度为σ，节点的繁忙感应时间和冲突检测时间都为σ，节点入网请求的传递过程的服务时间长度假设为4σ。则第n轮的入网时间=x(1+Pc(x))Nσ/Ps(x)+4Nσ+Δ。

T(x)为最优窗口函数。将数值代入T(x)得到的量化结果如图4所示。

从图4中看到，当x=1.4时，T(x)取极小值。其意义是当窗口系数选择一个合适的数值时，可以保证节点加入到网络所使用的时机数最小。时机数小就意味着冲突的数量少，节点加入到网络的时延越小，节点入网的效率就越高。所以，面对不同规模的无线自组织网络，应该选择适合的参数，以优化入网管理效率。

4 自组织应急通信网现阶段面临的问题及未来发展趋势

无线自组织应急通信网络相关技术发展到今天仍然存在许多问题，包括：网络设备、网络安全以及网络管理等；其中入网过程管理是基础也是关键，有关入网问题将成为今后自组织应急通信网络研究的重要方向。

由于无线自组织应急通信网络自身的特点使得网络具有很大的特殊性，也就面临普通网络所不存在的很多问题，诸如终端能量受限、CPU能力受限、资源受限等使得网络节点不选择或者无法执行复杂的算法。为了达到自组织网络安全要求和实现入网过程的快速认证，需要一种算法简单而安全的加密算法。因此，适用于自组织应急通信网络的快速安全的认证机制将成为今后的重要研究方向。

在不同的应急网络中对节点的安全性、入网的快速与否要求不同。如战场环境在节点入网时必须要保障节点的可信，否则将影响整个网络的安全，这就要求保障入网节点的高可信度。对于灾难现场，多数是为了搜集现场信息，只要能保障数据的正常传送即可，对安全性要求次之，对入网节点的可信度要求相对较低。由此可以看到，针对自组织应急通信网络需要一套标准，对不同的应急通信场景，定义相应的可信等级，统一地划分入网节点的可信等级。这些将成为标准化组网的重要课题。

5 参考文献
[1] 魏更宇, 张冬梅, 王枞, 等. 时间关键组网技术分析 [J]. 电信技术, 2009(12):24-26.
[2] 方旭明. 移动Ad hoc网络研究与发展现状 [J]. 数据通信, 2003(4):15-18.
[3] 刘勇, 陈剑波, 齐开悦. Ad hoc网络的安全机制 [J]. 信息安全与通信保密, 2005(9):66-69.
[4] 王海涛. Ad hoc网络的应用现状和发展趋势 [J]. 通信技术政策研究, 2010(1):32-42.
[5] 焦慧颖, 董晓鲁. IEEE802.16m标准的最新进展 [J]. 世界电信, 2007 (11):52-55.
[6] IEEE 802.16d. IEEE Standard for Local and Metropolitan Area Networks, Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems [S]. 2004.
[7] MIL-STD-188-220D. Department of Defense Interface Standard Digital Message Transfer Device Subsystems [S]. 2005.
[8] IEEE 802.16e. IEEE Standard for Local and Metropolitan Area Networks, Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems [S]. 2006.
[9] WANG Shieyuan, LIN Chihche, FANG Kuhan. Facilitating the Network Entry and Link Establishment Processes of IEEE 802.16 Mesh Networks [C]//Proceedings of the IEEE Wireless Communications and Networking Conference(WCNC’07), Mar 11-15, 2007, Hong Kong, China. Piscataway, NJ, USA: IEEE, 2007: 1842-1847.
[10] BIANCHI G. Performance Analysis of the IEEE 802.11 Distributed Coordination Function [J]. IEEE Journal on Selected Areas in Communications, 2000,18(3): 535-547.

魏更宇，日本东北学院大学工学博士，北京邮电大学计算机学院副教授，长期从事网络与软件安全、自组织网络、应急通信、P2P技术等方面的研究，已发表SCI/EI检索论文20余篇。

杨茗名，北京邮电大学计算机学院在读硕士研究生。