Ｒｅｓｅａｒｃｈ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ＨＯＬＳＲ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ ｆｏｒ Ａｄ—ｈｏｃ ｎｅｔｗｏｒｋｓ
ＨＵＡＮＧ Ｊｕａｎ．ＹＵ Ｊｉｎｇ—ｄｏｎｇ （Ｎａｔｉｏｎａｌ Ｌａｂｏｒａｔｏｒｙ ｏｆＣｏｍｍｕｎｉｃａｔｉｏｎ，Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｅｌｅｃｔｒｏｎｉｃ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ｏｆＣｈｉｎａ，
目前提出的针对异构移动Ａｄ ｈｏｅ网络的分级路由协议主
要有：ＨＳＲ用（ｈｉｅｒａｒｅｈｋａｌ ｓｔａｔｅ ｒｏｕｔｉｎｇ）、ＬＡＮＭＡＲ蚓（１ａｎｄｍａｒｋ ｒｏｍａｇ
ｐｒｏｔｏｃ０１）、ＨＯＬＳＲＩ”ｏｇｈｉｅｒａａｒｈｉｃａｌｏｐｔｉｍｉｚｅｄｌｉｎｋｓｔａｔｅｒｏｕｔｉｎｇｐｒｏｔｏｃ０１）。
为了在对等层级间交换群内部成员信息，ＨＯＬＳＲ协议引 入了ＨＴＣ（ｈｉｃｒａｒｅｈｉｅａｌ ｔｏｐｏｌｏｇｙ ｃｏｎｔｒｏｌ ｍｅｓｓａｇｅ）消息，群首将自 己群的成员列表填入ＨＴＣ报文并广播给其它同群的群首，通 过相互了解群成员信息来建立起到其它群的成员节点的路由 表项，即群问路由表。通过交换ＨＴＣ消息，群首能及时掌握 同级的其它群首的群成员列表，从而为群间投递数据报文提 供了路由依据。 ２．２传统ＨＯＬＳＲ存在的问题 ２．２．１群的数量及规模
ｔａａｃｅＶＯＣｔ一，ＡＯＤＶ）两种类型嘲。ＯＬＳＲ、ＡＯＤＶ的节点都有多
个接口，然而都采用了平面结构，这种方法没有考虑接口的通 信能力，增加了控制开销。
然而，在大多数军事战术情况下，ＡｄＨｏｅ无线网络是异构 的，组成的移动设备的配备接口具有不同的通信能力，频带，电 池寿命等。为了在异构ＡｄＨｏｅ网络解决这一复杂问题的路由， 可将网络细分为一个层次规模较小的网络，每个一级负责自己 的路由嘲。在分级路由协议中，节点根据自己的地理位置进行 分群，每个群由一个群首和多个普通节点组成。普通节点只知 道其群内的所有信息，群首节点除了知道其群内的所有信息， 还知道其它对等群的成员信息。这种方法每个节点只用维护 一个比较小的路由表，减小了资源开销，缩短了路南收敛时间。
情况下，节点采用Ｍ ＴＲＦＦＣ控制消息发送周期。３种情况下
控制消息发送周期如表ｌ所示。
表ｌ 不同网络状况下控制消息发送周期
Ｃ【Ａ
脏ＬＬＯ
Ｔｃ
盯ｃ
Ｌ ＴＲＦＦＣ
２ｓ
Ｍ Ｔ１谭ＦＣ
３ｓ
２ｓ
４ｓ
３ｓ
３ｓ
６ｓ
５ｓ
Ｈ ＴＲＦＦＣ
５ｓ
５ｓ
８ｓ
８ｓ
３ ＨＯＬＳＲ的设计及实现方案 本文在Ｌｉｎｕｘ ２．６操作系统上搭建ＨＯＬＳＲ路由协议的实
余敬东（１９６８～），男，副教授，研究方向为无
万方数据
２１４８
２００９，３０（９）
计算机工程与设计Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｄｅｓｉｇｎ
逻辑分级，不同的层级问采用不同的通信频率进行互不干扰 的独立通信。ＨＯＬＳＲ将性能低、单接口的节点被指派为低级 （一级），将较高性能的节点指派为中间级（二级）。二级节点拥 有两个接口，一个接口采用和一级节点相同的频段，另一个接 口采用不同的频段进行同级间的通信，在第二级的通信范围 比第一级大。性能最高的为最高级（三级），拥有两个或３个接 口，可同时与各级节点通信，同级问采用高速的点到点链路。 ＨＯＬＳＲ的网络结构如图ｌ所示。
０引 言
移动ＡｄＨｏｅ网络“１是由一组可移动的无线节点组成的多 跳无线网络。这种多跳无线网络没有基站一类的基础通信设 施，依靠节点之间在无线信道上的相互感知与协调，构成网络 通信环境，移动节点既是主机也是路由器。与有中心网络相 比，移动ＡｄＨｏｅ网更坚固，更耐用，而且不需要提供固定的骨 干设施，用户就可以通过无线网络瓦通。因此移动ＡｄＨｏｅ网 主要应用于军事ｌ二，以及一些紧急情况，如受灾地区的通信、 边远地区和勘探等场合的通信。
群首首先广播跳数为０的ＣＩＡ控制消息，邻近的节点收 到后加入该群，转发ＣＩＡ控制消息邀请更多的邻居加入该群。 若某个节点收到两个或多个Ｃ从，表示它同时处于多个群首 的覆盖范围中，它可以加入跳数最少的那个群。若有多个跳 数相等的ＣＩＡ，则选择第一个收到的ＣＩＡ的群首的群。
节点入群后，在群内交换ＨＥＬＬＯ及ＴＣ控制消息。ＨＥＬＬＯ 消息的格式定义了节点间可以交互的本地链路及ＭＰＲ选举 信息的内容和方式。ＨＥＬＬＯ消息中的信息对于成功完成链路 侦听、邻居探测和ＭＰＲ节点选举有着重要的意义。ＭＰＲ节点 利用本地广播和ＭＰＲ转发机制向网络洪泛ＴＣ消息。节点通 过接收ＴＣ消息完成对网络拓扑的掌握。
节点通过接收ＨＥＬＬＯ、ＴＣ消息完成对网络拓扑的掌握。 若网络为静态网络或者节点的移动较慢，网络的拓扑情况会
在一个相对较长的时间内保持相对稳定状态。这时，节点重
复发送及接收相同内容的ＨＥＬＬＯ及ＴＣ控制消息，造成资源 浪费。因此，只有当满足以下条件时才发送ＴＣ控制消息：
·当节点检测到两跳范围内邻节点发生变化时，重新计
ＨＯＬＳＲ通过分群机制来增加网络的可扩展性，群的数量 以及群内节点数会影响协议的性能：若群首节点数量过多，会 造成群的数量过多，群内平均节点数过少，浪费群首节点资 源；若群首节点数量过少，会造成群的数量过少，群内平均节 点数过多，群内路由表过大。这都会导致协议性能退化，为 此，采用以下机制平衡群的数量及规模：
Ｃｈｅｎｇｄｕ ６１００５４，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ａｔｔｒｉｂｕｔｅ ｏｆｍｏｂｉｌｅ Ａｄ—ｈｏｅ ｎｅｔｗｏｒｋｓ．ｔｈｅ ｐｒｉｎｃｉｐｌｅ ｏｆＨＯＬＳＲ ｈｉｅｒａｒｃｈｉｃａｌ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ ｉｓ ｓｔｕｄｉｅｄ，ｔｈｅｎ ｔｗｏ ａｓｐｅｃｔｓ ｉｓ ｉｍｐｒｏｖｅｄ，ｔｈａｔ ｉｓ ｔｈｅ ｃｌｕｓｔｅｒ ｎｕｍｂｅｒ ａｎｄ ｓｃａｌｅ ｃｏｎｔｒｏｌ，ｃｏｎｔｒｏｌ ｐａｃｋｅｔ ｒｅｄｕｎｄａｎｃｙ ｒｅｄｕｃｉｎｇ．Ａｎ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆＨＯＬＳＲ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ ｉｓ ｐｒｅｓｅｎｔｅｄ．Ｔｈｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｉｓ ｄｏｎｅ ｃｏｍｂｉｎｅｄ ｗｉｔｈ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆＣ，ｉｎｃｌｕｄｉｎｇ ｍｅｓｓａｇｅ ｍａｎａｇｅｍｅｎｔ，ｔｏｐｏ— ｌｏｇｙ ｃａｌｃｕｌａｔｉｏｎ，ｃｌｕｓｔｅｒ ｍｅｍｂｅｒ ｍａｎａｇｅｍｅｎｔ，ｒｏｕｔｉｎｇ ｃａｌｃｕｌａｔｉｏｎ．Ｂａｓｅｄ ｏｎ ｔｈｅ ｒｅｓｕｌｔｓ ａｎａｌｙｓｉｓ，ｔｈｅ ｒｅｓｕｌｔ ｓｈｏｗ ＨＯＬＳＲ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ ｉｓ ｓｉｍｐｌｅ，ｐｒａｃｔｉｃａｌ ａｎｄ ｓｕｐｅｒｉｏｒ ｐｅｒｆｏｒｍａｎｃｅ． Ｋｅｙ ｗｏｒｄｓ：Ａｄ－ｈｏｅ ｎｅｔｗｏｒｋｓ；ＨＯＬＳＲ；ｈｉｅｒａｒｃｈｉｃａｌ ｍｕｔｉｎｇ ｐｒｏｔｏｃｏｌ；ｃｌｕｓｔｅｒ；Ｌｉｎｕｘ
第三级
第二级
第一一级
Ｏ一级节点：●二级节点；▲三级节点
图ｌ ＨＯＬＳＲ网络结构
网络初始化时，高一级节点自动成为低一级节点的群首。 群首周期性广播Ｃｌｕｓｔｅｒ ＩＤ Ａｎｎｏｕｎｃｅｍｅｎｔ（ＣＩＡ）控制消息来邀 请其它节点加入自己的群，ＣＩＡ包含两个域：广播ＣＩＡ的群首 的接口地址和到该群首的跳数ｈｏｐ，最大值设置为８。
计算机工程与设计Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｄｅｓｉｇｎ
ＩＩ
·网络与通信技术·
２００９。３０（９）
２１４７
移动ａｄ．ｈｏｃ网络ＨＯＬＳＲ路由协议研究与实现
黄娟，余敬东 （电子科技大学通信抗干扰技术国家级重点实验室，四川成都６１００５４）
摘要：根据移动ａｄ．ｈｏｅ网络的特点分析了ＨＯＬＳＲ分级路由协议的工作原理，在控制网络中群的数量及规模、减少冗余控 制分组两方面进行了改进，并基于Ｃ语言提出了一种ＨＯＬＳＲ路由协议的实现方案。该方案结合了ｃ语言特点主要完成了消 息处理、拓扑计算、群成员管理、路由计算等功能。最后在Ｌｉｎｕｘ系统下实现了该方案，基于对实验结果的分析，验证了ＨＯＬ－ ＳＲ路由协议简单、实用、性能优越． 关键词：Ａｄ－ｈｏｅ网络；ＨＯＬＳＲ；分级路由；群；Ｌｉｎｕｘ 中图法分类号：ＴＰ３９３．０２ 文献标识码：Ａ 文章编号：１０００－７０２４（２００９）０９．２１４７．０４
度过快，不仅会加重网络的拥塞程度，还会导致节点单位时间 内收到大量的控制消息，浪费系统资源。若周期过长，影响节
点对拓扑情况的感知。因此，根据节点每秒收到的控制消息 数目，将网络情况分为Ｌ ＴＲＦＦＣ，Ｍ ＴＲＦＦＣ和Ｈ ＴＲＦＦＣ这３
种：当节点每秒收到的控制消息数月不大于３条时，节点采用
Ｉ，ＴＲＦＦＣ的控制消息发送周期：若节点每秒收到的控制消息 数目大于６条，节点采用Ｈ ＴＲＦＦＣ控制消息发送周期；其它
２ ＨＯＬＳＲ路由协议
２．１协议概述 ＨＯＬＳＲ协议是以节点性能的高低来进行群组的划分和
收稿日期：２００８－０５．１９：修订日期：２００８．０８．０５。 基金项目：国家自然科学基金项目（１０５７７００７）。 作者简岔：黄娟（１９８２一），女，硕士研究生，研究方向为无线移动自组织网的组网与路由技术； 线移动自组网、通信信号侦察、通信中的信号处理。Ｅ－ｍａｉｌ：ｌｉｖｅ６７４３＠，ｓｉｎａ．ｃｏｉｎ
表，邀请一跳邻节点数最多的节点升级为高一级节点。节点
收到邀请后确定自己为高一级节点并发送ＣＩＡ控制消息邀请 其它节点入群。
２．２．２冗余控制消息
节点加入群后，通过周期性交换控制消息建立路由表。 然而冗余的控制消息以及过于频繁的交Βιβλιοθήκη Baidu信息会占用过多的
带宽，造成资源浪费。减少控制报文发送的次数可以很好地
解决这个问题。为此，采用以下两个相应的机制： （１）采用条件触发机制更新网络拓扑
黄娟，余敬东：移动ａｄ－ｈｏｅ网络ＨＯＬＳＲ路由协议研究与实现
２００９，３０（９）
２１４９
验平台，完成协议算法的实现工作。 在Ｌｉｎｕｘ操作系统中，系统的路由功能划分成两部分来实
现。一部分在操作系统的内核中，叫做包转发功能块，它在表 驱动的进程基础上，处理直接传递给系统网络外出接口的数 据包。另一部分处在用户空间，叫做包路由功能块，管理路由 实际的路由协议和设置包的路由。内核中的包转发功能块要 维护一张内核路由表，在每个数据包通过相应的网络外出接 口，发送给下一跳之前，需要参照这张表来确定路由。而内核 中的这张路由表又是通过用户空间的包路由功能块形成的， 在用户空间的包路由功能块作为一个路由守护进程，在后台 运行。这个路由守护进程负责和其它网络节点进行控制信息 交流，使用适当的路由算法进行路由选择。这两部分功能块 的相对独立有利于内核中数据包的流动，不会出现不必要的 切换费用，也提供了增加或改变路由协议的灵活性，包路由功 能块放在内核以外也有助于减轻ＣＰＵ的负荷和内存的占用。
ｌ移动Ａｄｈｏｅ网络的路由技术
在多跳和移动通信环境下，节点间的通信关系随时都可 能发生变化，需要采用一定的自组织算法，及时掌握动态变化 中的网络拓扑结构，为网络中的通信寻找路由。
大部分移动Ａｄ Ｈｏｅ网络的路由协议假设节点具有相用 的处理和通信能力，即网络是同构的。对于同构的网络，路由 协议根据路由发现策略可分为：主动路由协议（如ｏｐｔｉｍｉｚｅｄ ｌｉｎｋ ｓｔａｔｅ ｒｏｕｔｉｎｇｏ“，０ＬＳＲ）和按需路由协议（如０１１．ｄｅｍａｎｄ ｄｉｓ—
万方数据
（１）设群的群成员数为ｍ，定义平均群内最少成员数为
ＭＩＮ＿ＡＶＲＧ＿ＭＥＭ
ＭＩＮ＿ＡＶＲＧ＿ＭＥＭ＝丁１×％熊警
ＭＡＸ—ＡＶＲＧ—ＭＥＭ＝ｚ×ｊ专；丢篙 平均群内最多成员数ＭＡＸ ＡＶＲＧ—ＭＥＭ
（２）若加＜ＭＩＮ ＡＶＲＧ ＭＥＭ，该群首节点降级为低一级节
点，群内节点加入其它群。 （３）若所＞ＭＡＸ ＡＶＲＧ ＭＥＭ，该群首节点根据群内路由
算ＭＰＲ，发送ＴＣ控制消息通知其它节点； ·当节点收到其它节点的ＴＣ控制消息，同时修改了本节
点的路由表时，需要把这一情况通知其它节点； ·节点采用一个比较大的周期发送ＴＣ控制消息，这种
冗余消息可以避免消息丢失或出错引起建立错误的网络拓
扑情况。 （２）采用自适应算法更新网络拓扑
ＨＯＬＳＲ采用固定周期换控制信息，若发送控制消息的速