Ad Hoc网络性能测试关键技术研究

本文首先介绍了Ad Hoc网络及其相关协议的主要特点，根据网络特性提出了性能测试的体系结构。围绕体系结构中的不同测试内容，提出相关的测试方法，并详细讨论了网络性能的评估手段和测试环境的设计。

随着现代通信技术的进步，人们对移动通信需求的不断增加，移动通信系统，如个人笔记本计算机，掌上型PDA设备等得到了迅速普及。但目前多数的移动通信系统是集中式控制的(有中心的)，网络的运行要基于预先架设好的网络设施。这两个特点使得有中心的移动通信系统对有些特殊场合来说并不适用。例如，战场上部队快速展开和推进、发生地震或水灾后的营救。这些场合的通信不能依赖于任何预先架设的网络设施。此时，需要系统能实现临时快速自动组网，结点要能移动。

Ad hoc网络是一种有特殊用途的对等式网络。它使用无线通信技术，网络中的结点互相作为其邻居(在其直接通信范围内的结点)的路由器，通过结点转发实现结点间的通信。它又被称为多跳网络(multi-hop network)、无固定网络设施的网络(infrastructure less network)或自组织网络(self-organized network)[1]。

由于Ad

12 ALT="图1：网络接入时延的测试方法。"> hoc网络工作在分布式移动环境中，并且网络带宽非常有限，所以要尽量减少通信对端的交互信息数量。多跳特性是Ad hoc网络的另一个显著标志。由于结点的无线通信距离有限，Ad hoc网络中的结点不一定都在其它所有结点的直接通信范围之内，而且受电磁干扰，地形干扰或天气影响，结点的通信距离也会有所改变。所以当结点并非直接可达时，需要中间结点的转发才能实现通信。也就是说从源结点到目的结点是多跳(multi-hop)连接的。

传统的基于有线网络的共享广播信道接入技术(ALOHA、CSMA系列)只能在共享的信道上使用。而Ad hoc网络具有多跳性，不是共享网络。所以Ad hoc网络的信道接入协议要充分考虑多跳带来的隐终端、暴露终端和公平性等问题[2,3]。Ad hoc网络中结点是移动的。结点的移动性造成网络的拓扑结构不断变化，这对接入协议和路由协议都提出了新的要求。首先接入协议要能够感知到结点移动造成的链路通断，并把这些信息报告给路由协议。路由协议要根据链路状态的变化修改自己的路由表。传统的基于固定网络的路由协议显然不能直接用于拓扑变化频繁的 Ad hoc网络。所以Ad hoc网络路由协议成了研究的焦点。Ad hoc网络中，结点的移动性也会影响网络的性能[4]，这需要相应的机制来解决。

由于影响Ad Hoc性能的因素很多，并且错综复杂，仅仅考虑有限的测试指标并不能够反映网络的真实性能, 所以Ad Hoc网络性能测试系统需要对网络进行全面的分析与理解，根据网络特性确定测试内容，有针对性地选择测试方法，进而构建与具体网络应用相适应的网络测试环境。

网络性能测试体系结构

Ad Hoc网络协议主要包括网络接入层协议(MAC)和路由协议。不同层次的协议由于所完成的功能不同，所以具有不同的测试指针。在网络测试中，要合理评价网络性能必须充分考虑不同层次的协议在性能上的差别。同时，对于不同的网络应用来说，各个层次协议性能对网络整体性能的影响也不尽相同。

Ad Hoc网络性能测试按照网络功能层次进行区分，主要分为以下三个方面的内容：通信终端物理性能测试，接入层协议测试和路由协议测试。

1. 通信终端物理性能测试

通信终端种类很多，包括数字电台、PDA、移动笔记本电脑等等。不同的无线终端由于硬件配置不同，其物理性能也不尽相同。物理性能测试内容主要包括：

12 ALT="图2：路由重建时间的计算方法。">

* 数据发送速率：即终端设备可支持的最大传输带宽，对于多信道系统而言，还需要测试最大可用带宽。

* 传播距离：即设备的通信范围，主要与终端的发送功率，接收门限(信噪比)有关。多跳网络中，传播距离会对网络的拓扑关系产生重大的影响，也是MAC层协议设计通常需要考虑的问题[2][3]，也是影响网络吞吐量的因素之一。

* 差错控制能力：无线信道通常是不可靠信道，所以需要相应的差错控制能力，保证在一定的信道误码率下，可以完成正常数据通信。

2. 网络接入层性能测试

网络接入层(MAC)解决了隐终端和暴露终端的问题[2][3]。MAC层协议的性能会直接影响网络的整体性能。MAC层协议是Ad Hoc网络组网协议的基础，也是网络结点通信的第一步，只有高效、公平、有序地组织网络中的所有通信结点的链路层通信能力，才能保证上层网络互联协议(路由协议)的正常运行。网络接入层性能测试内容主要有：

* 接入时延：结点从有数据需要发送到数据的实际发送的时间间隔。是反映单个结点接入效率的重要参数，但是不能反映网络整体性能。

* 网络吞吐量：接入协议的性能还体现在网络吞吐量上，由于无线网络数据帧的碰撞会导致所有的发送方都要退避一段时间，然后重新发送数据，这就必然对系统的吞吐量产生影响。

* 优先级：网络中的结点按照优先级排序，优先级高的结点比优先级低的结点有更低的平均接入时延，这一点在同时承载数据业务和话音业务的网络中显得尤为重要。

* 公平性：优先级然保证了优先级高的结点有更低的接入时延，但是网络接入协议还必须同时保证优先级低的结点不会“饿死”，同等优先级的结点还要有相同或接近的接入时延参数。

3. 路由协议性能测试

路由协议的任务是维护网络拓扑，为结点之间的通信提供及时准确的路由信息，保证报文按照协议所提供的路径正确到达目的结点。针对现有Ad Hoc网络路由协议的特点，性能测试主要包括以下几个方面：

* 端到端时延与吞吐量：路由协议所处理的是源结点到目的结点之间的路径选择信息，所以源结点到目的结点之间(端到端)的行为最直接的测试内容就是时延和吞吐量。但是，这两个参数都与MAC层协议的效率直接相关。

* 路由发现时间(也称为路由重建时间)：直接说明了路由算法的效率，即从无法根据路由表得到路由到得到可用路由的时间。需要注意的是，这个测试参数适用于需求驱动路由算法(反应式)[1][5]和具有事件触发更新功能的路由表驱动型路由算法(先应式)[1][6]。

* 路由表收敛时间：对于路由表驱动型路由算法而言，路由协议在运行期间，路由表从初始状态到路由表稳定状态通常会有一个自动更新的过程，这个时间通常称为路由表收敛时间。

* 路由协议的效率：任何路由协议在运行过程中，都要有一定的路由协议开销，用于在结点之间维护网络的拓扑信息。对于无线网络而言，网络带宽非常有限，协议开销直接影响网络带宽的利用率，进而影响网络的扩展性。所以路由协议的效率也是我们重点考虑的测试参数之一。

性能测试的基本方法

Ad Hoc网络的性能测试的主要内容已经在第二节中进行了阐述，由于物理层的测试内容只涉及到点对点之间的通信。而且，无线终端设备厂商一般会事先提供相应的物理层参数，所以下面讨论的性能测试方法只与网络接入层和路由协议有关。

1. 接入层协议性能测试方法

(a) 接入时延测试

12 ALT="表1：给网络不同的性能测试内容赋予不同的加权值可以更加客观地反映网络的性能。">

结点对所有到达发送缓冲区的数据包用时间戳进行标记，在该数据可以发送后，即满足下列条件，收到CTS数据帧并且是缓冲区最先要发送的报文，再记录下数据可以成功发送的时间。这个时间与时间戳记录的时间相减即接入时延，在系统测试时，通常计算结点所有数据包的平均时延。接入时延测试如图1所示：

(b) 优先级测试

网络中的优先级可以分为结点优先级和报文优先级。在统计意义下，优先级的测试要依赖于平均接入时延的计算。如果是对网络结点按照优先级进行区分，性能测试就计算不同结点的平均接入时延。如果网络只支持报文优先级，就要对不同类型的报文进行区分，分别计算平均接入时延。对于同时支持结点优先级和报文优先级的网络，测试要更加复杂。

(c) 公平性测试

公平性测试的依据主要是平均网络接入时延，优先级高的结点比优先级低的结点具有更小的平均接入时延。同时，不同优先级结点之间的时延差距要相对明显。例如，最高优先级结点与最低优先级结点之间的时延差距不到5%，就说明MAC层的网络优先级机制是失败的。

2. 路由协议性能测试方法

路由协议所有的性能测试参数都需要在多跳网络中实际测量得到，要根据Ad Hoc网络的特点合理运用路由协议的性能测试方法。需要特别指出的是，网络的覆盖范围，网络结点的移动性等对网络路由协议的参数会产生较为明显的影响 [4]，上述问题将在第4节进行讨论。Ad Hoc网络的路由协议主要有如下几方面的特征[8]：

*分布式特征：该特征是Ad Hoc网络最突出的特征。

*无环路：路由协议的重要约束条件之一，可以简单地采用TTL(生存时间)来对“兜圈子”的报文进行控制，但是考虑协议的效率通常采用更好的办法。

*需求驱动(反应式)：路由协议并不主动维护路由表，当发现无法得到目的结点路由后，需求驱动路由协议发送路由请求信息。

*路由表驱动(先应式)：路由协议主动维护网络中的拓扑，定时更新路由表，有的协议还有更新触发功能，可以更快地发现新的可用路由。

*安全问题：安全性是Ad hoc网络面临的另一个大难题。Ad hoc网络使用无线通信技术，容易被监听和干扰。加上Ad hoc网络一般被使用在特殊场合(军事、救灾等)，安全问题更加突出。在无线链路安全性非常脆弱的情况下，路由协议的安全性对于网络尤为重要。

*休眠期：电源能量对于基于移动网络的终端非常重要，路由协议需要支持设备的休眠功能，不要在休眠期仍然进行路由信息的交互。

*非对称链路支持：无线网络的非对称性必然会导致非对称性路由，路由协议必须能够在源结点和目的结点之间建立非对称路由，这样就增加了协议的复杂性。

根据路由协议的特点，提出路由协议性能测试方法。

(a) 路由协议端到端时延

测量主机之间时钟同步是端到端测量重要的技术基础。利用GPS、PSTN、CDMA等网络的外部时钟源来实现测量主机间同步。虽然精度高，但费用昂贵且在测量主机数量很大时难于实现。一般端到端时延测量可以通过RTT(Round Trip Time)获得，但是由于无线链路广泛存在着链路非对称的情况，所以需要测量端到端的单向时延。[10][11][12]对单向时延的测量提出了基于某种最优化目标来确定测量参数的方法。根据不同的要求，提出相应的优化目标，利用线性规划模型进行求解，最终到达提高单向时延参数精度的目的。

(b) 路由发现时间

12 ALT="图3：“直线型”结点分布。">

当路由协议发现当前维护的路由条目失效或无法为目的结点提供可用路由时，会主动发出路由请求，网络中的邻居结点会根据路由请求的内容或者转发路由请求，或者向源结点报告可用路由，或者什么都不做[1][7]。从发送路由请求到得到可用路由的时间就是路由重建时间，如图2所示。

(c) 路由协议的效率

网络中路由信息占信息传输总量的百分比。对于路由协议的效率参数，可以利用外部测量的方法，即在网络中加入监听结点并分析数据内容的方法来计算路由协议效率。但是这种方法的开销较大，如果对协议本身进行修改，本地计算可以大大减少网络开销。在路由协议中，在路由维护信息送到发送缓冲区之前进行修改：

#IFDEF CACULATE_EFFECIECY

int num_of_routing_message++

#ENDIF

这样利用下面的公式：

12 ALT="">

可以得到路由协议的效率参数。

网络综合性能评估

网络综合性能评估必须充分考虑不同网络环境对网络性能的影响，结合网络应用背景对网络性能进行综合评估。

网络环境对网络性能的影响主要有以下几个方面：

(a) 网络覆盖范围：结点的数目和分布率(通常结点较多的情况下)决定了网络覆盖范围，

(b) 网络连通性：通常是网络结点的平均邻居数目，在图论的意义下，也就是网络结点的“度”[13]。

(c) 拓扑变化频率：表征了网络拓扑变化速率。

(d) 链路容量：有效的链路带宽，即可利用的链路带宽，标称带宽与可用带宽的差别主要由于接入协议，编码和数据帧封装时导致的错误。

(e) 非对称链路：网络中非对称链路数量会对网络性能产生影响。同时，不同的路由协议在非对称链路网络中的工作效率也是不同的。

(f) 网络流量模型：路由协议在平衡流量网络或突发性网络中的表现是不同的。

(g) 移动性：结点的移动特性对网络的性能也会产生影响，例如在军事上，通信结点一般都以集群的方式向某一方向或地域运动，所以同一集群各个结点之间移动的相关性较强，而不同集群之间的移动相关性则不是十分明显。这一点对路由协议性能产生重要影响。

(h) 休眠结点数量：网络中休眠结点数量多可以延长终端的待机时间，同时可以有效地减小网络中路由协议的开销。协议对休眠结点的处理方法以及效率也是影响网络性能的因素之一。

在特定的网络应用环境中，可能会具有上述某些重要特征，不同的网络应用会对不同层次的协议有不同的性能要求。对同一层次的协议，不同的应用也会对各个网络性能参数有不同的要求。例如：协议A在大规模网络中性能非常好，协议B在小规模网络中性能优于A，如果应用场合是一个小规模网络，应该优先选择B协议。实际测量中的情况不是这个简单，需要多方面的性能综合考虑，可以根据应用特点的不同，给网络不同的性能测试内容赋予不同的加权值，这样可以更加客观地反映网络的性能，如表1所示。

其中，

12 ALT="">

所以加权值是归一化参数。

如果各个参数之间具有相关性，如移动性和连通性之间相互影响，简单地用加权值并不能科学地反映网络性能差别，利用层次分析法[9]，可以更加准确地对不同网络的性能进行评估。

网络测试环境设计

1. 结点分布范围与移动特性

分布范围一般有三种模式：

(a) 均匀分布(随机分布)

所有结点的地理位置是完全随机的。在给定范围内，如30km*30km或50km*50km，结点可以在任何位置请求与其它结点进行通信，同时网络结点以随机的方式移动。

(b) 直线型分布

12 ALT="图4：“星型”分布。">

直线型分布也是一种非常常用的结点分布形式，如车队在高速公路行进中的情况就符合这种分布特征。实现的这种分布式特征的方法是，让结点在一个狭长区域随机移动。用这种方式下，结点之间的通信主要依靠直线拓扑结构的网络，如图3所示。。

(c) 星型分布

在许多分区结构的网络中，成员结点与群首通信组成了本地网络，也称为“群”或“簇”。这样的网络，结点分布是一种星形分布。如图4所示：

分群网络中，可以构造多个星型分布的子网，这样可以测试网络在分群网络的性能。

2. 网络结点的流量

网络结点的流量也会对网络性能产生影响。在测试平台中，针对不同的应用环境，应该配置不同的结点数据流量规则，以合理地对网络性能进行测试。

(a) 均衡流量

这种方式下，各个结点流量均相同，从应用层看，就是各个结点的业务类型相同或相近，需要提供相同的数据传输业务保障能力。

(b) 非均衡流量

在某些应用场合，如军事应用中，各个结点之间所承担的任务不同，结点的数据业务需求也不相同。例如，指挥官所在的网络结点可能需要大容量的实时数据业务，而单兵使用的通信结点可能数据量较小。对应于分群网络，群首结点的数据通信需求要远大于成员结点。

本文小结

由于网络的分布性，结点移动的不确定性和无线链路的不可靠性，Ad Hoc网络性能测试成为目前无线网络技术中的难点之一，本文讨论了Ad Hoc网络测试的体系结构。同时认为由于Ad Hoc网络的具体应用场合不同，要根据网络特点对相关内容进行测试，同时要对测试内容综合评估。网络测试环境对网络性能有重要影响，所以要针对具体的网络应用背景选择网络环境进行性能测试。只有各个方面的因素综合考虑，并采用不同的测试环境和测试手段才能够准确地评估Ad Hoc网络的性能。

参考文献

[1]、 Elizabeth M.Royer and C-K Toh. A Review of Current Routing Protocols for Ad hoc Mobile Wireless Networks. IEEE Personal Communications Magazine, April 1999

[2]、V.Bharghavan,A.Demers,S.Shenker,and L.Zhang. MACAW:A Media Access Protocol for Wireless LANs. Proceeding of ACM SIGCOMM 1994

[3]、 J.Deng and Z.J.Haas. Dual Busy Tone Multiple Access: A New Medium Access Control for Packet Radio Networks. IEEE ICUPC'98, October 1998

[4]、Matthias Grossglauser, Davis Tse, Mobility Increases the Capability of Ad Hoc Wireless Networks, INFOCOM2001.

[5]、Zygmunt. J. Hass, A New Routing Protocol for the Reconfigurable Wireless Networks, http://www.ee.cornell.edu/~hass/wnl.html

[6]、 Josh Broch , David A Maltz, etc . A Performance Comparison Of Multi-Hop Wireless Ad Hoc Network Routing Protocols, MobiCom'98 1998 ACM

[7]、David B. Johnson . "Routing in Ad Hoc Networks of Mobile Hosts" Computer Science Department 1991

[8]、RFC 2501 Ad Hoc Network Route Measurement

[9]、姜启源编著 《数学模型》清华大学出版社 北京 1999年

[10]、 MOON, S.B., SKELLY, P.AND TOWSLEY, D., Estimation and Removal of Clock Skew form Network Delay Measurements. In proceedings of the IEEE INFOCOM Conference on Computer Communications, page 227-234, March 1999

[11]、 DYER, M.E., Linear Time Algorithms for Two and Three Variable Linear Programs. SIAM Journal on Computing. 14 (1983) , 759-776.

[12]、 MEGIDDO, N., Linear Time Algorithms for Linear Programs in R3 and Related Problems. SIAM Journal on Computing 12 (4) (1983) , 759-776.

[13]、陈志平，徐宗本编著 《计算机数学－计算复杂性理论与NPC、NP难问题的求解》科学出版社　北京　2001年