用电信息采集中无线网络路由算法的研究
2010-03-11潘小山朱小兰
彭 风 ，潘小山 ，朱小兰 ，余 红
（1.河南信阳供电公司 信阳 450003；2.华北电力大学 北京 102206）
1 引言
在用电信息采集系统中，本地通信采用的是短距离无线通信方式，由于受距离的限制，集中器并不能与所有的采集器直接通信，因此引入无线网状网。它可将多个采集终端节点随机组成无线自组织网络，将采集到的数据以多跳的方式发送到集中器中，由集中器实现数据存储和远程传送[1]。路由问题是无线传感网络网络层的核心问题，也是现阶段国内外研究的热点。因为路由算法直接决定数据如何中继和路由，而路径的选取直接影响表的工作时间，进而影响功耗。因此，对用电信息采集系统中的路由问题进行研究是十分必要的。
目前，对无线网状网路由算法的研究主要是将应用于传统Ad-hoc网络的路由算法进行改进，使其符合无线网状网的特性。传统的路由算法有DSDV、DSR、AODV算法等[2]，其中AODV算法最具代表性。它是一种典型的按需路由算法，业界已经提出了很多其改进算法[3]，在开销、延时、分组投递率等方面得到了改善。
在用电信息采集中，由于无线信道的带宽有限，在数据传输过程中可能造成拥塞，这将导致网络延时，不利于抄表工作的顺利进行。另外,在国家大力倡导节能低碳的今日，尽可能地降低功耗也是路由算法需要考虑的问题。因此本文将根据用电信息采集系统的特点，在传统AODV算法的基础上，采用拥塞控制机制的同时，对网络层进行功率控制，提出了一种基于拥塞控制与功耗最小的路由选择算法。
2 用电小区路由需求分析
2.1 用电小区拓扑分析
由于各个小区居民楼布局不同，地理位置分布迥异，居民楼内电表的布局位置也各有不同，因此存在多种网络拓扑结构。下面以一种小区拓扑结构举例说明，如图1所示。每幢居民楼有6层，分为4个单元，每个单元每层楼有2个用户，2个用户的电表集中放在本层楼楼道里的电表箱中，每个电表箱都配有一个采集器，通过RS-485总线与电表相连，这样，每层楼有4台采集器。集中器的位置不定，户内户外均可，可以根据实际情况任意确定。本小区将集中器设在A楼的一层，作为一台采集器使用，不仅便于数据采集，还节约了成本。为了使通信可靠进行，还装有中继终端进行中继转发。图1中虚线表示两个设备可以直接互联（这两个设备叫做邻居节点，两者可以直接通信，不需要由其他节点转发），两个设备之间若没有惟一的直线连接，则表示两者无法实现直接互联，只能靠中继转发。现实中的网络是错综复杂的，为了便于说明，图中只标出了有限的连接。
从图中可以看出，若A楼的采集器A5要将用电信息发往集中器，其通信路径可以是A5—A6—A7—集中器或A5—A2—A3—集中器，可见需要通信的设备之间有多条通路，该如何选择最佳的通路呢？这即是无线传感网的路由问题，需要设计一种算法来指导其选择最佳路径传输数据。路由算法的选择对于数据传输的可靠性和有效性至关重要。路由算法设计时须考虑的因素很多，如节点移动性、节点能量、负载均衡等，其路由判据也有最小跳数、最小开销、最小功耗等多种，因此需要根据不同的场景设计出适合该环境的路由算法，以达到最佳路由性能。
2.2 用电小区路由算法要求分析
在用电信息采集系统中，所有采集器、电能表的位置都是固定的，因此路由算法不用考虑节点的移动性。由于该系统受干扰冲突、通信距离等因素的影响，如果仅以最小跳数作为路由判据，而不考虑路径上的业务通信量，抄表过程中可能会因为设备同时上电进行数据传输而造成拥塞，使该路径的链路质量恶化，更甚者造成数据丢包，网络的吞吐量下降。数据丢包数越多，就不能满足用电信息采集系统中对电表数据抄收率的要求。因此，在设计路由算法的时候，使算法具有拥塞自适应功能是非常必要的。
另外，对于发送节点的某一发射功率，接收节点的信号强度与传输过程中的信道衰减有关。用电信息采集系统中各通信设备之间进行数据传输的过程中，途中会遇到墙、门、金属等多种阻碍，这都将造成信号衰减。信号衰减过大，将影响网络通信质量，可能导致数据丢失，不能保证用电数据的抄收率。因此，在网络层路由算法中进行适当的功率控制，不仅能减小信道干扰从而提高通信链路质量，而且能减少链路功耗以满足节能低碳经济的要求。
因此，根据用电信息采集系统的需求特点，下面将提出一种基于拥塞控制与功率控制的AODV改进算法。它依据节点的拥塞状况来决定数据分组的发送，并根据消息的优先级来确定数据发送的顺序。在路由选择问题上，通过对网络层的功率控制进行研究，改变传统以最短路径为路由判据的思想，选择功耗最小的路径进行数据传输，使其能更好地满足用电小区的抄表要求。
3 基于拥塞控制与功率控制的AODV改进算法
3.1 AODV路由算法
AODV算法是一种按需路由协议，它仅在需要路由时才由源节点启动路由发现过程。算法的基本过程如下：当源节点S要发送信息给目的节点D时，如果发现自己路由表中没有到目的节点D的路由，S便发送路由请求RREQ包给所有的邻居节点，请求其邻居节点帮忙查找到节点D的路径。每个接收到RREQ包的节点，都记录下上一跳节点信息，若自身不是目的节点，则广播RREQ包。通过这种洪泛方式，RREQ包会被广播转发至目的节点D。目的节点D接收到RREQ包后，反向沿着该RREQ包传来的路径通过单播的形式发送路由回复RREP(route reply)包，同时在中间节点记录下到达目的节点的下一跳，当S收到RREP包时，从源节点到目的节点的路径已经建立起来。为了维护路由信息，节点通过周期性地广播Hello消息来检测链路是否失效。当某节点在规定的时间内没有收到响应时，说明链路发生中断，当下次有数据要发送给目的节点D时，原路径失效，要重新发起路由请求过程[4]。
AODV算法简单易行、避免了路由环路选择最短路径来传输数据。但它的路由过程没有考虑节点的拥塞状况，从而很容易导致整个网络的拥塞，减少了网络生存时间。本文将采用拥塞控制机制，并将功耗作为一个约束条件来选择最佳路由，从而优化AODV算法的性能。
3.2 AODV的改进算法
3.2.1 拥塞状态判别
当源节点和目的节点之间的路由建立后,就可以对此路由中间节点的拥塞状态进行监测。判断一个节点的拥塞程度可以有不同的衡量参数如链路带宽、丢包率、平均队列长度、缓冲区溢出量、重传分组的数量、分组的平均时延等[5]。本文选择节点的平均队列长度L作为衡量拥塞程度的指标。平均队列长度L定义为节点队列瞬间长度与队列总长度之比。给L设定上下限值：Lmin和Lmax，根据L值确定节点的3种拥塞状态:当0
3.2.2 发射功率的计算
为了在算法中进行功率控制，需要分别计算出链路中各节点间传输分组所需的功率，然后将整条链路上发射功率的总和作为QoS路由的代价函数[6]。路由建立后，节点就按照它们计算出的发射功率来传输数据分组。如果节点A要给节点B通信，A以最大的功率Pmax发送RTS，节点B收到A的RTS后仍然以最大功率Pmax发送CTS，当节点A接收到CTS时，根据它的接收功率Pr和它的发送功率Pmax计算它发送数据的功率Pds，公式如下：
其中，Pmin是所必需的最小接收功率，c为常量。节点A就按计算出的Pds发送数据。Pds一般比Pmax要小，从而达到节能的目的。
设从源节点到目的节点有M条路径，依次为R1，…，Rm，N1，…Nk为某一条路径Ri上的节点。则代价函数计算如下：
最后，我们选择代价函数cost值最小也即功耗最小的一条路径进行数据传输，有效地减少节点的能量，从而延长节点的工作时间。
3.2.3 路由发现过程
当源节点S需要和目的节点D通信，而其路由表中又没有到目的节点的有效路径时，它会启动一个路由发现过程。源节点便向邻居节点广播路由请求RREQ分组。在原AODV算法基础上，需要在路由请求分组RREQ中为每个节点增加一个拥塞状态信息及其发射功率Pds值。每个收到RREQ分组的中间节点根据自己的拥塞状态来进行相应的响应：（1）如果节点状态为normal，并且是第一次收到该分组，则记录上游节点地址、拥塞状态和Pds等信息，该节点按照式 （1）计算其发送功率Pds值，将Pds值加入到RREQ分组中，并察看路由表中是否有到达目的节点且序列号大于等于RREQ分组中的序列号的无拥塞路由，若无，节点记录报文并以Pds作为发射功率转发此RREQ分组；若有或该节点就是目的节点，则将RREQ分组的信息复制到路由应答分组RREP中，并向源节点发送RREP分组；（2）如果当前节点拥塞状态为 congestion，延迟一段时间DELAY-TIME之后，再进行如（1）步骤中的相同操作，在这段延迟时间中若存在其他状态较好的链路则提前建立起路由[7]；（3）如果当前节点拥塞状态为 serious，不管有没有到目的节点的有效路由都直接丢掉该RREQ分组，并向源节点发送反向抑制报文抑制拥塞。中间节点转发RREQ分组，直到目的节点收到RREQ分组，此时路由发现过程结束，RREQ分组所经过的路径即为可行路径。最后到达目的节点的路径可能有多条，本文选择代价函数即功耗最小的那条作为最佳路径，目的节点沿可行路径向源节点发送路由应答分组RREP。当源节点S收到RREP分组后，连接即建立。路由发现过程流程如图2所示。
本算法中，为了更好地进行拥塞控制，还采用了基于事件驱动的多优先级拥塞控制策略，即根据需要传送数据的紧急程度来设定优先级。用电信息采集系统中，可能因为某种原因主站突然想采集某一居民用户的即时用电数据，此事件为紧急事件，设为高优先级级别，需要得到快速处理及响应。而通常情况下的对每户用电数据进行周期性的采集，设为低优先级级别，可以滞后处理。在每个数据包中都携带其优先级别信息，当很多数据包在某一节点排队等候发送的时候，节点可以先判别数据包的优先级别，先发送优先级别高的，再处理优先级别低的，这样可以有效地降低节点的拥塞度，从而提高系统运行效率。
3.2.4 路由维护过程
在进行用电信息采集的通信过程中，可能会由于断电或故障引起某些设备无法正常工作，从而导致链路断开，原先建立的路由失效，这样会使通信中断。此时如果仍按原路由发送数据，就会导致数据丢失。为了保证电表数据的抄收率，每一轮抄表结束后都需要对路由进行维护，从而保证下一轮抄表过程正常进行。
在用电信息采集系统中，集中器轮询抄表间隔一般为5 min，因此路由维护的周期选择为4.5 min。即每次抄表结束后，节点以4.5 min为周期广播Hello消息来检测链路是否失效。当某节点在有限的时间内没有收到任何响应时，说明链路发生中断。当某节点检测到链路断开后，不是直接进行本地修复，而是根据自己当前的拥塞状态来确定是局部修复还是向上游报错：（1）如果节点处于normal或congestion状态，就可以进行本地修复，在本地寻找新的路由；（2）如果节点处于 serious状态，则直接向上游节点发送路由出错分组RERR，由上游无拥塞节点进行路由重建，从而修复路由。
为了修复失效路由，本算法引入动态功率控制机制，即动态地改变节点的发射功率，从而调整网络的拓扑结构和选路，使全网性能得到优化。节点的发射功率与其通信距离是紧密相关的，发射功率越大，在其他因素相同的情况下，其通信距离越远[5]。因此，当某一节点检测到路由失效后，其上游节点收到RERR分组后，就可以动态地增大自身的发射功率，使其通信距离变远，足够跳过失效的节点，避免因信号强度过小所带来的重新选路和连接等过程，从而保证数据的可靠传输。如图3所示，当蓝色的节点失效后，其他节点可以通过加大其发射功率，越过失效节点，从而修复路由。当然，如果某节点经维护后又重新能正常运行了，此时，在满足通信要求的情况下，又可以适当地降低其发射功率，以达到节能的目的。
4 结束语
针对用电信息采集系统的网络拓扑特点，本文在原有AODV路由算法的基础上进行了改进，路由发现阶段基于事件驱动的多优先级拥塞控制机制，减少数据丢包率，保证了数据传输的可靠性。并且考虑了链路间的功率损耗，以最小功耗作为路由判据，达到了节能的目的，有效地延长了设备的工作时间。路由维护过程采用动态功率控制策略，与传统路由算法相比，减少了路由修复的时间。因此，将该路由算法应用于用电信息采集系统中，能达到较好的路由性能。由于设计路由需要考虑的因素众多，比如负载均衡、网络容错等因素本文都没有涉及，在以后的工作中，要对其他因素深入研究，使得网络路由更加优化。
1 于飞,胡继珍.低压电力无线集抄系统数据传输路由算法研究.电力系统保护与控制,2010,38(1):66～69
2 洪锡军,张激.无线自组网路由协议研究.计算机工程,2005,31(8):105～107
3 薛楠,张靖.Ad-hoc网络中AODV路由算法的改进.哈尔滨商业大学学报,2006,22(3):39～41
4 王斌.无线传感器网络AODV路由协议的实现.计算机与现代化,2009,(1):86～89
5 刘桂开,王洪江.一种基于辅助路由的拥塞自适应协议.系统工程与电子技术,2010,32(5):1070～1077
6 梁云,魏明.基于AODV有功率控制功能的QoS路由协议PCQ_AODV.通信技术,2008,41(4):84～86
7 吴建新,朱翠涛.联合拥塞控制的AODV路由算法研究.光通信研究,2009,(3):61～64
