基于国网规范的无线自组网路由算法改进

邵立芳,孙濮东,楼珊珊

（北京南瑞智芯微电子科技有限公司,浙江杭州,310013)

0 引言

我国最具发展潜力的现代应用技术之一是无线自动抄表系统，智能抄表领域的热门研究课题则成为通信技术的设计方法。主要涉及三个核心问题的是无线自动抄表通信技术的研究：低成本是首要问题，无线自动抄表系统成本直接影响用户的接受程度其本身是由于涉及到千家万户；其次是低功耗问题，协议的设计和网络通信技术协议的设计都必须要以节能为前提；最后是自组网问题，保证控制中心命令和表计用量数据及时准确的传输，自愈能力和可靠性也是无线自动抄表网络的重要要求。研究对象是国网的无线自动抄表系统体系结构，针对第三个核心问题自组网问题进行详细的分析研究。

1 国网规范的自组网路由设计及缺陷

国网规范中微功率无线自动抄表系统的组成是散布在一定地理区域的大量静态通信节点，整个系统釆用从上至下的主从模式，层次性非常明显。本地通信网络中通常包括采集器集中器和表计三类通信节点，集中器中的微功率无线模块指定为中心节点，采集器和表计中的微功率无线模块为子节点，中心节点管理所有子节点，并收集、计算和处理节点的一些关键信息。

图1 国网规范中中心节点直接管理所有子节点

国网规范中路由表的建立是在组网过程的场强收集阶段完成，由中心节点发出场强收集命令，逐层收取每一层节点的邻居节点 信息，信息收取完成后，中心节点根据收集到的节点信息，结合自身的路由算法，计算出符合一定QOS 的单条或多条路径。

源节点和目的节点间存在多条路径是平面式结构的路由算法最大的优点之一，因此可以通过多条路径减少拥塞，传输业务流，消除可能的“瓶颈”问题，但是由于微功率无线自组网具有动态的拓扑（节点可能会进入或退出网络）、有限的带宽等问题，这种平面式结构在节点数目增多时的路由开销很大，可扩展性较差。

局限是每个常用的优秀路由协议都具有的，系统开销的有效降低是由于DSR 充分使用源路由发现和路由缓存机制。源路由的开销是每个数据包都包含的，当数据包经过众多的中间节点时，也会导致开销的增加。该算法具有明显的局限性的原因是CBRP首先提出用分簇算法来提高路由的可扩展性，但是基于单路径路由技术，频繁的进行路由重启和路径修补，开销是巨大。

1.1 改进的簇的选择与建立方式

采用适当的分簇多路径算法，构造分层的拓扑结构是解决国网规范路由问题最有效的方法之一。能够优化网络带宽的应用，提高共享信道的利用率；有效地减少交换路由控制信息的开销，强化节点的管理；容易实现局部网络同步；支持大规模的无线网络，可扩展性好。

基于簇的多路径动态路由算法的主要思想是在分簇算法中将网络分成单元簇和中心簇，这种分层可以实现路由开销最小化，同时提高网络的可扩展性，有效适应节点数目多和节点密度大的网络。

该算法主要有三部分组成：簇的选择和建立、可靠路由的建立、动态路径维护。

1.1.1 簇的结构

CMDSR 的簇结构，将网络分为三级层次，第一级是节点层，每个节点相距簇首一跳，第二级为单元簇，负责管理多个节点按一定的算法和规则集结生成簇，同时受中心簇的管理和控制，第三层为中心簇层，中心簇为一组单元簇的集合，管理控制所有单元簇。

图2 簇的结构图

1.1.2 簇的初始化及更新

自组网中的每个节点进行标识及令牌赋值首先是对簇的初始化。利用规定的簇首选举算法选举簇首，构建各自的邻居集合，相邻节点间交互信息，实现簇的初始化。成为簇首的节点向所有邻居节点广播，未加入其它簇的节点获取通告以后，立即应答，宣布加入该簇。一个节点只属于一个簇。

簇成员保留它能侦听到的簇首节点的ID 是所有节点采用分布式方法交换信息。导致簇及簇成员改变的主要原因是网络节点的加入或退出，网络的拓扑也随之改变。

1.1.3 中心簇首的选择

图3 簇的更新方式示意图

中心簇首管理所有成员簇，中心簇不遵循成员簇首的选举方式，直接指定集中器中的微功率无线模块即中心节点为中心簇首。

1.2 可靠路由建立

1.2.1 路径查找

当源节点s 试图建立到目的节点d 的连接时，向它的簇首发起一次路径请求消息（RREQ），簇首收到RREQ 消息后，判断目标节点是否与源节点在同一簇中，如果相同，则通知节点启动路由查找程序；不在同一簇中，则向中心簇首报告路径请求消息，中心簇首根据网络拓扑结构建立起源到目标的路由查找导向队列{S，C2，…，Cm-1，D}，并把队列信息发送到源节点。

源节点s 向其邻居节点发送RREQ 消息，RREQ 包含最低可靠性需求Plower和已经路过的链路及相应路径的可靠性Pacc等信息，每个RREQ 消息都有唯一的请求ID，每个网络节点可以唯一确定一个RREQ，Pacc域初始设置为1。

当中间节点更新完RREQ 消息后，将会把这些信息复制多个转发给它的邻居节点。中间节点拒绝向已经出现VR 域中的邻居节点发送消息，确保RREQ 消息不会在网络中循环。

表1 RREQ 消息

1.2.2 路径选择

算法分为两步，第一步是路径分类，按照路径可靠性递减的顺序分类排列，这些已分类的路径集称为候选路径集。第二步是非交差路径选择，从候选路径集中选择出一组非交差的路径，这组路径都满足最低可靠性要求。通过以上两步选择出来的路径称之为真实路径。

当目的节点完成了路径选择后，将会向每一条非交差路径发送一组RREP 消息到源节点，格式如表2 所示。

表2 RREP 消息

1.3 动态路径维护与修补

由于网络的动态特性，路径可能在任意时刻被中断，为了保证可靠的的网络连接，必须进行路由维护以保证端到端的可靠性。

路由维护分为以下三种情况：

a) 第一种是在传输过程中，源节点会向该路径发送RCHK消息检查路径情况原因是端到端的可靠性低于Plower的要求时，并设置暂停以等待RCHK-RP，接收到RCHK-RP 后，源节点在目的节点路径重新计算端到端可靠性。如果可靠性满足，则源节点使用该路径继续进行传输数据。

b) 第二种情况是在传输路径中的某一中间节点NODEi移动后，网络拓扑发生变化，造成路径可靠性变差或路径中断，该节点的簇首判断变化路径的前一节点NODEi-1和后一节点NODEi+1是否属于本簇成员。如果是则将该NODEi的信息直接迁至簇首，并通知前一节点NODEi-1设置一个暂停时间，根据路径查找算法，来形成很多NODEi-1到NODEi+1新链路，用这些链路代替原来中断的路径。如果NODEi-1，NODEi，NODEi+1不属于同一簇，则向中心簇首报告变化情况，并将有关信息迁至中心簇首，由中心簇首来实现路径维护。

c) 第三种是当路径中的某个簇消失或者几乎所有路径都破坏的情况下，要立即初始化一次新的路由发现但是源节点不做任何检查。

2 实验仿真与性能分析

2.1 实验设计

为集中比较不同的路由算法，假定物理层、链路层及其它层的参数都是固定不变的。

设置节点在1500 m X 500 m 内的区域移动，为了发现单路径和多路径的区别矩形区域一定要扩大平均路径长度，；节点采用随机分布；暂停时间设置为0～900 s 显示不同的移动性对性能的影响。节点数目为50～500 个，用来观察节点数目的增长对性能的影响。。

表3 实验参数及其配置

2.2 性能计算结果

图4 说明了CBRP、SMR、CMDSR 不同移动速度的报文成功传输率。移动速度在0 ～ 30 m/s 的任何值时，CMDSR 的传输成功率比CBRP 和SMR 都高。不管移动节点速度如何改变，CMDSR和SMR 能够得到相对稳定的传输成功率，这是实验模拟结果证明的。

图5，图6 说明了单路径路由开销低于多路由原因是多路径路由搜索路径花费的代价要比单路径路由花费的代价要高。CMDSR 相对于SMR 代价要低，特别是节点数目增加时，CMDSR 的开销要比SMR 小的多，这是因为利用簇的层次管理来进行路由搜索，比起在整个网络进行搜索代价小的多，特别是网络规模越大，基于簇的路由算法（CMDSR 和CBRP）相对于平面结构路由算法（SMR）的开销越小。

3 结语

只有关注自组网的差异性才能设计出更高效的系统，利用分簇算法的优点，将网络分成两层簇结构，路由发现被迁移到中心簇层进行，控制路由发现阶段泛洪开销大的缺点，实现路由开销最小化。为了进一步提高网络的可扩展性必须要有效处理节点数量增多和节点密度增大的问题，；在现有的国网规范中，想要提高组网速度，增加网络的可扩展性，那么基于簇的动态路由算法具有重要的参考使用价值。

图4 不同移动速率报文成功传输率

图5 不同的速度下的节点开销控制

图6 不同节点数目开销控制实验图

[1] 刘树刚.微功率无线自动抄表系统设计新方法及其应用研究[D].湖南：湖南大学，2011.

[2] 王阳，唐龙江.无线自组网通信技术在配电网监测中的应用[D]，安徽：黄山供电局.2008.

[3] 电力用户用电信息采集系统通信协议第4 部分：基于微功率无线通信的数据传输协议[S]，国家电网公司 2013：36-118.

[4] 安耀辉，王新安，李辉，苏金树，等.移动自组网中的先进路由算法与路由协议[M].北京：科学出版社，2009：50-138.

[5] Johnson D，Maltz D.Dynamic source routing in Ad Hoc wireless networks.//Imielnski E,Korth H.Mobile Computing.Amsterdam：Kluwer Academic Publishers，1996.

[6] 安耀辉，卢锡城，彭伟等，MANET 中基于簇的动态多路径路由.计算机研究与发展，2006，3(43).

[7] Ephremids A，WieselthierJ，Baker D J.A design concpt for reliable mobile radio networks with frequency hopping signaling.//Proceedings of the IEEE，1987，75(1).

[8] Gerla M ,Tsai T C.Multucluster,mobile multimedia radio networks.ACM-Baltzer Journal of Wireless Networks ,1995,1(3):255-265.

[9] Alwan A，Bagrodia R，Bambos N et al.Adaptive mobile multimedia networks.IEEE Personal Communication Magazine，1996，34-51.

[10] McDonald A B，ZNati T F,A mobility based frameworks for adaptive clustering in wireless Ad Hoc networks.IEEE Journal on Selected Areas in Communications，1999，17（8）：1466-1487.

[11] Lin C R，Gerla M.Adaptive clustering for mobile wireless networks.IEEE Journal on Selected Areas in Communications，1997，15（7）：1265-1275.

[12] Bhatnagar A，Robertazzi G.Layer net：a new selforganizing network protocols.//Proceedings of the IEEE MILCOM，1990：845-849.

[13] Chen W L，Jain N，Singh S，ANMP：Ad Hoc network management protocol.IEEE Journal on Selected Areas in Communications，1999，17（8）：1506-1531.

[14] 安耀辉，卢锡城，彭伟等，MANET 中一种基于簇的动态多路径路由算法.软件学报，2007，18(4)：987-995.

[15] Nasipuri A,Das S R.On-demand multi-path routing for mobile Ad Hoc networks,IEEE ICCCN,Boston,1999:64-70.