引言

无线自组织网络（AdHoc）是一种自治系统，由于其拥有自组织、自维护、无需基础设施、组网迅速等优势，使得AdHoc网络非常适合于应急通信、短距离通信等场合。但是，当网络中的节点处于密集区域比如无线抄表网络中节点密集的小区或者地震灾后应急通信网络中人员密集的区域时，现行的很多无线AdHoc网络协议容易引起不必要的退避、冲突，低效率的路由建立机制，使得密集区域下的自组织网络效率不高。因此，研究优化节点密集区域中的AdHoc网络路由协议和相应冲突退避算法就非常有必要。

1 AdHoc网络协议与密集节点区域

由于无线网络存在单向信道、传输带宽有限，以及节点的能源和Flash ROM有限等问题，使得OSPF、EIGRP、RIP等大型成熟的路由协议不能直接应用于无线自组织网络。

目前，已存在数十种以AdHoc为网络环境的路由协议，常见的无线AdHoc网络路由协议可以分为主动路由协议、按需路由协议等。按需路由协议能减少更新周期，根据需求建立路由，在一定程度上减少了不必要的更新包和冲突。按需路由协议常见的是DSR（即动态源路由协议）[1]，DSR的基本思想是：不更新路由信息，在需要的时候发送路由发现请求帧，邻节点收到后会检索是否有到目的节点的路由，如果没有，则将自己的节点地址加入到分组的路由记录并转发给相邻的节点，直至目的节点返回路由应答分组。

密集节点区域的AdHoc网络如图1所示。当网络采用DSR协议时，由于DSR是按需建立和发现路由的路由协议，不需要周期性发送路由信息，这在密集节点区域非常有必要。但是由于在DSR发现和建立路由的过程中，存在盲目性，使得洪泛在区域内展开，效率下降。

图1 密集节点区域示意图

在实际应用网络中，密集节点网络可能是需要大量抄表节点的无线抄表系统，或者是采用大量传感器节点来监测鸟类、昆虫等小型动物生态习性的环境监测领域。在这些环境下，网络存在以下共性[2]：①区域内节点密度较高；②节点自身能量有限；③区域内的节点之间最多间隔四、五跳。

2 密集节点区域的路由算法GC_DSR

DSR泛洪式路由发现方式是自组网路由协议中的双刃剑,它提供了一种准确无误的路由发现方法,但同时也使得整个系统处在盲目地转发中。如果采用以DSR为基础的分群归簇协议GC_DSR（Group and Cluster DSR），在DSR按需协议的路由发现机制中，同时引入群首和簇首的概念，使得节点发送的路由请求只在群中产生，路径查询只在簇首间产生，则可通过限制路由请求的接收和转发范围来减少洪泛，提高传输效率。若图1网络采用GC_DSR路由协议，其网络的组建与形成、新节点的加入过程可以用图2表示。

图2 GC_DSR协议示意图

2.1 架构设计

基于分群归簇的DSR路由协议专为密集节点区域而设计，但是对于密集稀疏的网络同样适用。网络中的节点分为群首（备用群首）、簇首（备用簇首）、普通节点，具体的系统构架图如图3所示。

图3 分群归簇DSR协议系统架构图

分群归簇路由通信方式，使网络中的节点在路由发现和查询的时候，不需要考虑上层路由发现和查询过程，只需要与群首通信。所以，新节点在路由查询过程中或多或少地增大了群首和簇首节点的负担，但是减少了网络中的路由洪泛，效率提高了。

2.2 网络的建立与节点的加入

GC_DSR网络的建立：网络建立之初，最早的节点在没有找到其他节点的情况下，首先成为代集中节点，设置自己的层次号（Level Number，LN）为1；其他几个节点与代集中节点建立路由关系，其中5个成为簇首，LN为10，其他几个没有成为备用簇首，LN为11；选择部分与簇首直接相连接的节点为群首，LN为20，其他与簇首相连却不是群首的节点为备用簇首，LN为21；其他与群首相连且有子节点的节点则为30，剩下的为40。

新节点的加入：GC_DSR网络建立之后，当有新节点加入时，新节点按照DSR路由发现机制，广播路由请求包RREQ；接收RREQ对象为群首，新节点与相对应群的群首建立应答路由关系，群首向簇首报备新路由节点。

2.3 节点通信时的路由发现机制

节点需要通信时，新节点展开路由发现机制，发送路由查询，该路由查询只在群首中产生，如果没有查到直接路由，群首发给簇首，路由查询在簇首间展开，获得路由之后回复源节点，路径查询结束，通信开始。图2中的网络采用GC_DSR路由协议，当新节点A加入网络，并发送路由请求包至G节点时，其转发流程如图4所示。

图4 GC_DSR路由发现机制示意图

3 基于优先级的对数函数退避策略

在设置路由节点的频率时, 如果采用的是同频收发, 那么自然就会存在节点之间的同频干扰问题。为了解决这一问题,通常会引入CSMACA 机制。在网络层增加广播退避算法，采用统一退避，只有在退避时间结束后检测信道为忙时，才进入MAC层退避[3]。退避计算值采用基于优先级对数函数退避 (Priority Logarithmic Backoff,PLB)算法，可以有效地处理密集式分层网络的退避冲撞问题。

① 原则：优先级高的优先传输，优先级低的退避传输。在分群归簇DSR网络中，采用牺牲群首和簇首的方法来减少路由洪泛。群首和簇首的频度大，进而优先级高，这样可以增加效率，减少损耗，随后是传输信息的节点，新加入的节点优先级最低。每个节点有层次号LN，通过层次号实现优先级判断。

② 传输单元：也就是点对点传输双向成功的最大时间片（Base Time，T0），采用传输单元为基本单元的退避算法，可以有效利用传输窗口实现传输最大化。

③ 同级窗口：本退避算法使用优先级区别出不同级节点的退避值，同时使用竞争窗口(Contention Window，CW)进行退避，也就是在1～5之间随机退避。

④ 对数函数：退避计数器的值[4]为TW= T0×4×ln（LN）+T0×CW,其中CW=[Rand（）%5+1]。退避值前半部分为优先级值，后半部分为同级竞争窗口值,“Rand（）%5+1”指随机值范围为1～5。

对于同样的节点数，将退避时间进行分段不但不会增加碰撞概率，反而会减小碰撞概率。具体PLB算法的退避流程如图5所示。

图5 PLB算法退避流程图

4 GC_DSR路由协议在CC1110的实现

4.1 CC1110软件系统结构

GC_DSR路由协议应用于CC1110组成的网络时，网络中的单个节点采用CC1110无线单片机。CC1110可以无缝地运行分群归簇DSR协议栈，并提供通用回调函数，实现数据帧自动接收，大大提高通信效率和可靠性。本系统采用IAR Embedded Workbench7.60作为开发环境，整个节点系统程序流程如图6所示。

图6 节点系统程序流程图

4.2 GC_DSR路由协议帧结构

在使用GC_DSR路由协议并采用CC1110无线单片机收发数据时，都需要统一的数据帧格式。CC1110在节点接收信息的时候提供回调函数rxCallBack（void），使得通信效率变高，所发即所收。同时，研发者可以在回调函数中增加对路由标识、目的地址、层次号的检查，并设置节点系统状态标识，提高效率。GC_DSR帧格式如下所示。

5 算法对比分析与监听检测

5.1 算法对比分析

对于采用DSR路由协议的网络：当有新节点要在有k个节点的网络中通信时，新节点若没有该项路由缓存则需要广播路由。最快得到的最佳路由就是目标节点时邻节点，但其他邻节点会转发广播，若设置帧存活时间最大为6（同一个数据包最多转发6次），造成最少1次、最多k-2次无效转发。最慢得到最佳路由时，需要跨越3～6跳，平均需要转发k-2次无效转发。实际网络采用DSR路由协议，当新节点A加入网络，并发送路由请求包至G节点时，其转发流程如图7所示。

图7 DSR网络转发流程图

目标节点G会收到2条路由转发帧，分别从L和X转发而来,对应路径为AB(J)ILG、AB(J)DHXG。由于经过节点L的路径更优，会选择经过L的路由，并发RREP给A。其在G点的路由表显示如图8所示。

使用GC_DSR路由通信方式的网络：新节点通信时需要按照路由发现机制发路由查询（Route Query，RQ）给相对应的群首节点和邻节点，如果邻节点或者群首有，群首不向上查询，则没有转发数据包。群首转发给其他n（4～6）个群首，这个过程需要转发1次，没有无效转发；若没有查找到,则转发给其他m(1～3)个簇首，需要就增加1次转发，没有无效转发。考虑相同的退避机制下，使用分群归簇的DSR路由协议最多造成的转发为2次，没有无效转发，因此，比DSR路由协议更佳。实际网络采用GC_DSR路由协议，当新节点A加入网络，并发送路由请求包至G节点时，其转发流程可以参考图4。

目标节点G没有收到路由转发帧，而是H直接回复路由信息，对应路径为ABCDH（XG）。其在A点的路由表显示如图9所示。

图8 DSR网络目标节点G（07）接收显示L（12）、X（15）转发帧

图9 GC_DSR网络源节点G（07）接收显示H（08）回复帧

5.2 监听测试

利用CC1110无线单片机作为网络节点，在密集节点环境下，对DSR以及GC_DSR协议进行测试对比。

测试过程中，在空余的节点上烧录监听程序，使之成为网络监听（Catch Bag）节点，并在监听节点上使用串口连接计算机，用VC++编写的串口收发软件进行收发测试，统计结果如表1所列。

通过多次测试和监听结果显示：

① 在DSR网络中，有很多的洪泛帧（相同内容、不同TTL的帧）存在，只要是满足转发条件的路由帧，其他节点都会转发，这使监听节点甚至集中器会收到附近区域的转发帧和重发帧。而在GC_DSR网络中，几乎没有洪泛，转发的数量非常有限。

表1统计（10次平均）监听结果

② GC_DSR网络长时间运行之后，群首簇首节点明显比其他节点电量少，而DSR网络的所有节点电量都比较均匀。

③ GC_DSR网络的节点路由质量不高，网络中节点所获得的路由没有DSR网络获得的好，也就是节点路由并非网络中的最佳路由。

④ 设置节点根据重发情况改变亮灯，采用DSR网络的节点亮灯次数多，且多个节点多次出现。在GC_DSR网络中，新节点在寻找路由的情况下，亮灯次数多。

测试和监听结果表明，GC_DSR路由协议通过牺牲部分节点的能源以及节点路由的质量使得网络在减少洪泛、转发等方面做得更好；在丢包方面，协议把这个情况交给应用层或者源节点、目的节点的重发机制。

结语

采用GC_DSR路由协议并使用基于优先级的对数函数退避算法的无线自组织网络，在密集节点区域下，通过牺牲部分节点的能源以及节点路由的质量使得网络避免洪泛，能有效地传递路由信息，同时使得新节点实现了路由的透明查询与信息传递。