交通路灯监控系统的无线传感网链状路由算法*

任条娟，陈友荣，王章权

（浙江树人大学信息科技学院 杭州310015）

1 引言

随着我国经济建设的发展，城市化进程的加快，城市道路交通的路灯照明设施得到了长足发展，但与此相伴的是路灯电能消耗也呈逐年快速攀升的趋势[1]。由于传统路灯照明多以低效照明为主，电能利用率不到65%，电能浪费严重，因此提出一种采用LED灯和无线传感网技术的新型路灯监控系统。该系统通过在每个LED路灯旁放置无线传感节点，实时控制LED路灯的开关，检测和上报LED路灯的开关状态、温度、亮度、电流和电压等各种参数信息，一方面可通过无线网络实时存储信息到上位机的数据库中以备查询和分析，另一方面可实时提供各个LED路灯的工作状况，产生故障路灯维修表，提醒管理人员进行故障维护，减少人工巡视时间，提高处理设备故障效率，较好地实现了路灯的智能化管理。由于系统依靠无线方式组网，无需布线，扩展灵活，易于被采用，具有实施快速、方便，对道路环境没有任何影响，易于故障维护等特点，可有效提高能源利用效率，减少能源损耗，节约能源成本，具有较大的市场应用前景[2]。

目前，国内已有多家公司应用无线传感网的射频通信模块，推出各自的节能路灯照明控制系统。但是很多路灯监控系统没有考虑到无线传感网节点的分布受道路局限，呈现“管状”分布，基本上还是采用简单的链状路由或树状路由算法，造成节点能耗和数据传输时延分布不平衡。靠近Sink节点的节点数据传输时延低，但是会频繁地转发其他节点的信息而导致节点能耗高。远离Sink节点的节点数据通信时延高，但是由于转发少量的数据，所以节点能耗低。综合所述，在路灯监控系统的特殊应用场景中，数据传输时延和节点能耗是无线传感网两个相对对立的性能参数，需要研究一种新的链状路由算法，尽可能平衡网络节点能耗和数据传输时延。

2 国内外研究现状

相关无线传感网路由算法的研究已取得一些成果。参考文献[3]提出一个低功耗自适应聚类分层型(low energy adaptive clustering hierarchy，LEACH)算法。LEACH 算法包括Sink节点、簇头节点和传感节点3层网络结构。算法中传感节点发送测量数据到簇头节点，簇头节点融合簇内传感节点数据再通过簇头间多跳方式发送到Sink节点。在大规模或节点能量分布不均衡的无线传感网中，LEACH算法随机选择簇头节点，可能出现被选簇头节点集中在某一个特定的区域，覆盖不到整个监测区域，容易造成网络的分裂和节点能耗的增大。参考文献[4]提出一种链状路由算法PEGASIS(power-efficient gathering in sensor information system)。感应区域内的所有节点通过贪婪算法自组织成一条链路。在数据传播阶段，每一个节点接收距离最近上游邻居节点的感应信息，通过距离最近的下游邻居节点将融合后的感应信息发送给Sink节点。在该算法中，离Sink节点距离较远的节点会引起较多的数据时延。参考文献[5]提出带能量消耗的链状路由(chain routing with even energy consumption，CREEC)算法，通过以下两个策略提高网络生存时间：一是尽可能平衡每一个节点的能量分布；二是模拟节点的能量消耗，运行反馈机制节省传感节点的能量。参考文献 [6]提出一种高效节能的链状分层路由(energy efficient chain-based hierarchical routing，CHIRON) 算 法 。CHIRON算法的主要思路是将感应区域分成若干个较小区域，在这小区域内建立数据传输链路，从而减少数据传输时延和冗余路径。参考文献[7]基于PEGASIS算法的结构提出内部网格PEGASIS算法。该算法将感应区域分成若干个网格，每一个网格中节点可分为开始节点、传感节点和结束节点。网格开始节点和另一个网格的结束节点建立连接，最终网络中所有节点自组织成一条链路。参考文献[8]为优化传感器间通信，提出虚拟链的概念，定义虚拟链的边为多跳数据传输路径。为优化簇头节点和Sink节点的通信，提出簇头节点的调度规则，选择剩余能量最大的节点作为簇头节点。参考文献[5～8]提出各自的链状路由算法，但是它们都假设节点随机分布在感应区域内，没有考虑链状无线传感网节点的“管状”位置分布。因此，综合一些学者的观点，针对路灯监控系统的特殊应用场景，提出路灯监控系统的无线传感网链状路由 (chain routing algorithm based on streetlight monitoring system for wireless sensor networks，CRASMS)算法，尽可能平衡网络节点能耗和数据传输时延。

3 网络模型和假设

如图1所示，路灯监控系统的无线传感网主要由传感节点（也称路灯监控器，简称节点）、Sink节点（也称网关控制器）和监控中心组成。传感节点分布在道路两侧的路灯上，具有控制路灯开关、上报开关状态、调节路灯亮度等功能。Sink节点处于监控中心和各传感节点的中间，一般放置在十字路口或道路边，向上通过GPRS/3G方式同监控中心通信，向下通过无线传感网同各个传感节点通信，无需通信费用。Sink节点主要负责监控网络内的传感节点运行，将监控中心的命令下达给传感节点，将传感节点及线路信息反馈给监控中心。监控中心实现对传感节点进行远程数据访问和监控，包括参数配置、监控命令发送、路灯状态收集等。还能够根据路段日照和人车流量的变化设定路灯的开关控制策略，在满足基本照明的前提下节约能耗。

针对路灯监控系统的实际应用场景，假设其无线传感网具有以下特点：

·Sink节点和所有传感节点位置固定不变，都是静止的，所有传感节点均匀分布，Sink节点可根据实际需要，放置在十字路口和每一个道路边；

·由于网络预先规划节点的部署位置，因此Sink节点和传感节点能获知整个网络拓扑结构信息；

·所有传感节点具有相同的性能（如无线电最大发送功率、最大通信半径、节点间距离、能耗模型等）；

·所有传感节点都能感知数据，并通过直接或多跳的方式将数据发送给Sink 节点；

·由于每一个路灯上都配置专门的供电电路，因此网络所有节点的能量不受限制；

·所有传感节点的发送功率随着通信距离的变化而变化。

4 CRASMS算法

4.1 算法原理

如果节点j在节点i的通信半径内，则称节点j是节点i的邻居节点。如果dis

CRASMS算法由簇区域的划分、簇头节点的选择、簇内星型网络的建立、数据通信和处理4个过程组成。

图1 交通路灯监控系统的无线传感网模型

4.1.1 簇区域的划分

路由监控系统中无线传感网节点以预先规划的方式部署，Sink节点能获知算法所需要的节点信息 （包括节点的位置），传感节点能获知自身和周围节点的信息。如图2所示，当网络启动后，Sink节点启动簇区域的划分，根据传感节点和监测区域的位置信息，将道路同一侧的节点构成一条链路，每一个链路划分成若干个具有n个节点的簇区域 （n可根据节点的通信距离和实际应用需求确定）。接着，Sink节点发送节点簇区域确定数据分组 （内容包括每一个簇的节点个数n）。节点收到簇区域确定数据分组后，根据自身与Sink节点的拓扑关系，确定所属的簇区域。

图2 簇区域的划分

4.1.2 簇头节点的选择

如图3所示，簇头节点的选择有些类似LEACH算法。网络确定簇区域后，在每一个簇区域中采用贪婪算法（greedy algorithm）选择离Sink节点距离最近的节点作为簇头节点。经过一段时间后，簇头节点接收到Sink节点的簇头更新数据分组后转为传感节点，其同一簇区域中距离最近的上游节点选为簇头节点。如果簇头节点已经是簇区域内离Sink节点距离最远的节点，则表示簇头节点的选择已经遍历该簇区域的所有节点，重新选择离Sink节点距离最近的节点作为簇头节点，开始新的一轮簇头节点选择。为避免无线通信的干扰，道路另一侧链路的簇头节点选择方法与其相反，先选择离Sink节点距离最远的节点作为簇头节点，每隔一段时间慢慢变近。此过程重复执行，网络中所有节点都有机会当选为簇头节点。

图3 簇头节点的选择

4.1.3 簇内星型网络的建立

确定簇头节点后，每一个簇头节点广播一个簇网络建立数据分组，所属簇区域的节点收到簇网络建立数据分组后，反馈一个通知数据分组。簇头节点接收到通知数据分组后，将该传感节点放入路由表中。最终在每一个簇区域内形成一个星型网络，如图4所示。

图4 簇内星型网络的建立

4.1.4 数据通信和处理

完成上述步骤后，数据通信和处理过程开始，具体过程如下介绍。

图5 数据通信过程

如图5所示，网络数据通信分成传感节点的数据上报和Sink节点的命令发送两部分。传感节点的数据上报过程如下：每一个传感节点采集数据，将数据发送给簇头节点。簇头节点采用融合算法处理数据，将融合后的数据以簇头间的多跳路由方式发送给Sink节点。簇头节点转发其他簇头节点的两个标准：一是选择离Sink节点距离近的簇头节点，二是在其通信范围内选择离本簇头节点距离最远的簇头节点。Sink节点广播上位机的一些控制命令，如设置一些路灯的开关时限、立即开启和关闭某一路灯。该命令的发送过程如下：Sink节点通过簇间多跳方式广播命令数据分组。簇头节点接收到命令数据分组后，判断簇区域内是否存在被控节点。如果存在被控节点，则通知该节点，节点收到命令后解析命令并执行，反之，则转发给离Sink节点距离远的簇头节点。

在无线传感网中，由于感应物理介质的时空特性，相邻节点采集的信息（如温度和湿度数据）往往携带着大量的数据冗余，因此需要对数据进行融合[9]。簇头节点选择数据融合算法处理传感节点数据是CRASMS算法信息处理的关键，能有效节省网络节点的能量。本算法采用参考文献[10]的数据融合算法模型。在该模型中，节点i利用本地数据对其接收到的节点j原始数据进行压缩。用系数qij表示节点j的原始数据在节点i上的数据压缩比。假设qij与节点i和j之间的距离成反比[10]，即：

根据上述模型，簇头节点对接收到的数据采用两种不同的操作。对传感节点的原始数据，采用本地数据进行压缩。对其他簇头节点的数据，则直接转发。

4.2 算法实现

如图6所示，网络启动后，Sink节点开始获知算法所需要的节点信息。一种方法是Sink节点以洪泛方式向周围所有的邻居节点发送信息查询分组。如果邻居节点第一次接收到Sink节点的查询分组，则将自身的位置信息发送给Sink节点，再向其邻居节点转发信息查询分组，否则丢弃该信息查询分组。另一种方法是Sink节点通过上位机程序获知节点的所有位置信息。Sink节点收集所有节点位置信息后，启动CRASMS算法。算法具体实现步骤如下。

（1）进行簇区域划分。Sink节点根据传感节点和监测区域的位置信息，将道路同一侧的节点构成一条链路，每一个链路划分成若干个具有n个节点的簇区域。接着，发送节点簇区域确定数据分组。节点收到簇区域确定数据分组后，根据自身与Sink节点的拓扑关系，确定所属的簇区域。

（2）确定每一个簇区域的初始簇头。道路左右两条链路，一条选择簇区域中离Sink节点距离最近的节点作为簇头节点，另一条链路选择簇中离Sink节点距离最远的节点作为簇头节点。

图6 CRASMS算法的流程

（3）通过簇头节点和传感节点的通信，在每一个簇区域内建立星型网络。

（4）启动数据通信和处理，完成数据的上报和命令的发送。经过一段时间，跳到步骤（5）。

（5）Sink节点广播簇头更新数据分组，如果簇头节点的选择已经遍历该簇区域的所有节点，则开始新一轮簇头节点选择，否则簇区域中距离最近的下游邻居节点或上游邻居节点当选为簇头节点。跳到步骤（3）。

循环执行上述步骤，实现CRASMS算法。

5 仿真实现和分析

5.1 仿真能耗模型

典型的无线传感网节点能耗主要由无线数据收发产生，其中ETx(g,d)表示发送节点发送g bit数据到距离为dij的接收节点所消耗的能量；同样ERx(g)表示接收节点接收g bit数据所消耗的能量。因此，节点发送模块的能耗ETx(g,d)由发送电路电子能耗和信号放大器部分的电子能耗组成。发送电路电子能耗固定为，其中g代表所发送的数据量，Eelec代表收发单位比特数据时电路的电子能耗。信号放大器部分的电子能耗与节点发送功率有关，由于采用Friss自由空间模型且节点根据通信距离随时调整发送功率，因此其电子能耗与通信距离有关。接收模块的能耗ERx只考虑接收信号时的电子能耗gEelec。具体的计算式如下（假设发送g bit的数据量，发送距离为dijm，最大通信距离m，收发单位比特数据时电路电子能耗nJ/bit，放大单位比特信号时所需要的电子能耗 εfspJ/bit/m2）[11]：

5.2 仿真参数设置

在算法仿真时，不考虑计算、数据融合、信息查询分组收发等能耗，也不考虑数据传输过程中超时重发、出错等能耗，只考虑数据无线通信能耗。考虑无线传感网节点实际通信距离和路灯的实际间隔，建立网络仿真区域（所有节点的位置分布纵坐标一致，横坐标间隔20 m），选择的仿真参数见表1，计算网络平均节点能耗和数据传输时延。其中平均节点能耗=所有节点将数据发送到Sink节点的总能耗/节点个数。平均数据传输时延=所有节点将数据发送给Sink节点的总跳数/节点数。

表1 仿真参数

5.3 仿真结果和分析

5.3.1 簇区域节点个数n参数的研究

研究簇区域节点个数n对网络节点能耗和数据传输时延的影响。考虑路灯监控系统的实际应用场景（大多数无线传感节点的最大通信距离是80 m），假设各个路灯间的距离是 20 m，则 n的取值范围是 1、2、3、4。选择 30、50、70、90、110、130、150、170 个无线传感网节点，分别计算当 n=1、2、3、4时CRASMS算法的平均节点能耗和数据传输时延，具体仿真结果如图7和图8所示。

图7 网络平均节点能耗

如图7所示，当n不变时，随着节点个数的增加，平均节点能耗增大。这是因为：随着网络规模的扩大，由于所有节点都需要发送数据，中间节点数据发送量变大，需要更多的能量转发数据，因此平均节点能耗变大。当节点个数不变时，n=2时网络平均节点能耗最小，n=1时的能耗次之，n=4时能耗最大。这是因为：当n=1时，在CRASMS算法中每个节点都是簇头节点，其直接选择离Sink节点近且在其通信范围内离本节点最远的簇头节点转发数据，通信距离较大，根据能耗式(2)和式(3)，节点能耗也较大。但是当n=2时，传感节点直接选择距离较近的簇头节点，通信能耗较小，因此，n=2时节点平均能耗比n=1时小。此后随着n的继续增大，簇区域的节点个数增多，传感节点的通信距离增大，因此网络平均节点能耗也增大。

如图8所示，当n不变时，随着节点个数的增加，平均数据传输时延增大。这是因为：随着网络规模的扩大，根据链状网络的特性，处于数据传输链路末端的节点离Sink节点距离变大，其数据的传输需要更多的转发跳数。当节点个数不变时，n=4时平均数据传输时延最小，n=3时次之，n=1时最小。这是因为：随着n的变大，簇区域的节点个数变大，更多的簇内节点直接发送数据到簇头节点，因此算法降低了数据通信的转发跳数。

图8 平均数据传输时延

总之，在CRASMS算法中，节点能耗和数据传输时延是相互制约的。当选择较大的n值时，CRASMS算法更多偏向于降低数据通信时延，当选择较小的n值时，CRASMS算法更多偏向于降低节点能耗。因此，可根据实际应用需求选择合适的n值。

5.3.2 算法仿真结果比较

路灯监控系统的节点规模大，通常一个Sink节点需要管理200个以上的节点。在这大规模的链状网络中，节点数据传输时延是其一大挑战。为了降低数据传输时延，仿真中选择n=4的CRASMS算法。为了验证算法的有效性，比较LEACH （传感节点成为簇头节点的概率是0.25）、PEGASIS和CRASMS算法。

由于LEACH算法随机选择簇头节点，在本场景中如果节点通信半径dmax过低，容易造成很多节点不能与簇头节点通信，因此仿真中需要选择较大的各算法节点通信半径。选择 30、50、70、90、110、130、150、170 个无线传感网节点和其他表1中的参数，分别采用LEACH、PEGASIS和CRASMS算法计算网络平均节点能耗、平均数据传输时延和它们的均方差，具体见表2和表3。

表2中，LEACH算法的网络平均节点能耗最大，而且节点能耗分布不均衡，能耗均方差也最大。无论是网络平均节点能耗还是均方差，PEGASIS算法比CRASMS算法都略低，但是两者相差不大。这是因为：监测区域中LEACH算法随机选择簇头节点，簇头节点分布不均衡，容易造成有些节点直接选择距离很远的簇头节点发送数据，导致节点能耗变大而且分布不均匀。在PEGASIS算法中，节点沿着链路选择距离最近的下游邻居节点发送数据。在CRASMS算法中，节点选择簇区域内的簇头节点发送数据。这两个算法的节点通信距离较短，因此平均节点能耗不大，节点能耗分布比较合理。总之，CRASMS算法克服了LEACH算法能耗较大的不足，保持了PEGASIS算法在能耗方面的优点。

表2 各算法的网络平均节点能耗

表3中，PEGASIS算法的平均数据传输时延最大（可表示为（1+N）/2），而且数据传输时延分布不均衡，时延均方差也最大。而LEACH和CRASMS算法无论是平均数据传输时延还是均方差，两者相差不大。这是因为：在PEGASIS算法中，节点沿着距离最近的下游邻居节点将数据发送给Sink节点。离Sink节点的距离越远，节点数据传输时延越大，因此PEGASIS算法的平均数据传输时延大而且分布不均匀。而LEACH和 CRASMS算法选择聚类方法，簇内节点直接发送数据到簇头节点，簇头节点通过簇头间多跳路由将数据发送给Sink节点，而且每一个节点都有机会成为簇头节点，这在一定程度上降低和平衡了节点数据传输时延。

表3 各算法的平均数据传输时延

总之，CRASMS算法保持了PEGASIS和LEACH算法的优点，克服了这两个算法的不足（与LEACH算法比较，降低了平均节点能耗；与PEGASIS比较，降低了数据传输时延），将网络平均节点能耗和平均数据传输时延保持在较低水平。

6 结束语

针对交通路灯监控系统的特殊应用场景，提出路灯监控系统的无线传感网链状路由算法，尽可能平衡网络节点能耗和数据传输时延。本文首先提出了由传感节点、Sink节点和监控中心组成的路灯监控系统无线传感网模型和算法假设。其次，详细阐述CRASMS算法的簇区域划分、簇头选择、簇内网络建立、数据通信和处理4个过程和具体算法的实现步骤。接着，介绍算法的能耗模型和仿真参数。最后，仿真分析簇区域节点个数n对算法平均节点能耗和数据传输时延的影响，比较LEACH、PEGASIS和CRASMS算法。

仿真结果表明：CRASMS算法保持了PEGASIS在节点能耗方面和LEACH在节点时延方面的优点，克服了PEGASIS在节点时延方面和LEACH在节点能耗方面的不足，将平均节点能耗和平均数据传输时延保持在较低水平。但是CRASMS算法只是通过仿真验证，还没有运用到实际硬件上，因此未来的工作是搭建一个路灯监控系统的测试平台，在该平台上验证算法的有效性。

1 张雪松.浅谈城市路灯照明的节能与环保.科技创新导报,2011,17(17):152

2 孙凤杰,王桢.基于路灯单灯状态监控的无线链状网络路由算法的研究.计算技术与自动化,2011,30(4):85～88

3 任条娟,杨海波,陈友荣.Sink节点移动的无线传感网生存时间优化算法.传感技术学报,2012,25(5):683～690

4 Heinzelman W R,Chandrakasan A,Balakrishnan H.Energyefficientcommunication protocolforwireless micro sensornetworks.Proceedings of The 33rd Ann Hawaii Int Conf,Hawaii,2000

5 Lindsey S,Raghavendra C,Sivalingam K.Data gathering algorithms in sensor networks using energy metric.IEEE Transactions on Parallel and Distributed System,2002,13(9):924～935

6 Shin J，Suh C J.CREEC:chain routing with even energy consumption.Journal of Communications and Networks,2011,13(1):17～25

7 Chen K H,Huang J M,Hsiao C C.CHIRON:an energyefficient chain-based hierarchical routing protocol in wireless sensor networks.Wireless Telecommunications Symposium,2009(1)

8 Chen Y L,Lin J S.Energy efficiency analysis of a chain-based scheme via intra-grid for wireless sensor networks.Computer Communications,2012,35(4):507～516

9 Yen L H,Cai M Z,Cheng Y M,et al.Energy optimization for chain-based data gathering in wireless sensor networks.International Journal of Communication Systems,2007,20(7):857～874

10 Hua C Q,Yum T P.Optimal routing and data aggregation for maximizing lifetime of wireless sensor networks.IEEE/ACM Transactions on Networking,2008,16(4):892～903

11 Rickenbach P V，Wattenhofer R.Gathering correlated data in sensor networks.Proceeding of DIALM-POMC,New York,2004

12 陈友荣,俞立,董齐芬等.基于近邻算法的无线传感器网络功率控制.浙江大学学报（工学版）,2010,44(7)：1321～1326