基于RSSI定位的多障碍低速组网算法

李峰+李世伟

摘 要：针对大型建筑物内部无线自组网组网算法存在数据采集不全、采集周期长等缺陷，提出了多障碍环境下基于RSSI的低速组网算法。为保证数据的可达性，该算法以实际节点连通状态进行定位并构建虚拟网络，节点间通过相互探测的方式进行路由选择，以节点接收的RSSI和节点间的实际通信距离作为选择依据。通过该算法，可以有效提高大型建筑物内部自组网数据的可达性，在多障碍、低速网络环境下具有较高的应用价值。

关键词：RSSI；虚拟网络；数据可达性；低速组网算法

DOIDOI：10.11907/rjdk.171172

中图分类号：TP312

文献标识码：A 文章编号文章编号：1672-7800（2017）008-0046-04

0 引言

无线传感器网络（Wireless Sensor Network，WSN）是由大量集成有信息采集、数据处理和无线通信功能的节点通过无线通信方式组成的无线自组网多跳网络[1]。无线抄表技术是无线传感器网络发展的产物，它取代了传统的人工抄表方式，是无线传感网的一个重要应用。重庆理工大学设计的基于GPRS的无线抄表系统[2]，基本可以实现无线抄表要求，但成本较高，不适合大面积使用；山东农业大学利用ZigBee设计的无线抄表系统[3]，虽然可以实现自组网，但信号穿透性不强、灵敏度低及抗干扰能力差等众多因素，导致该系统很难应用于实际生产环境；重庆大学提出的低成本和低功耗的无线抄表算法[4-5]，虽然用在建筑内部环境，但数据可达性无法保证。

为了解决目前无线抄表技术存在的成本高、穿透性差、信号传输距离短以及数据可达性差等问题，本文提出一种适用于多障碍的大型建筑物室内环境中的无线自组网算法——基于RSSI的多障碍低速组网算法，主要采用降低信号的传输速度提高信号的衍射能力，以此提高信号的可达性，保证数据的交付性。由于传输速度较低，因此采集周期较长，通过基于方向角与最短距离算法，减少路由跳数，缩短传输距离并减少传输时间。本文以信号强度作为下一跳的选择依据，提高数据的可达性和可靠性。通过本文提出的算法，可以有效地解决多障碍、低速网络环境下的数据传输问题，同时还可以避免路由空洞问题。

1 相关工作

1.1 基于逻辑拓扑结构的路由协议AODV

AODV协议[6]是逐跳地按需距离向量路由协议。AODV协议建立路由时，源节点广播发送路由请求RREQ数据包，每个接收到RREQ的中间节点记录到源节点的逆向路径，然后重新广播RREQ数据包。当RREQ数据包到达目的节点时，利用数据包中的逆向路径发送RREP。收到RREP数据包的中间节点，记录到目的节点的路径并转发RREP数据包。节点之间需要通过广播hello消息来维护本地邻居表以及一跳范围内的链路。AODV协议由于节点间需要定期广播hello数据包以及进行路由发现和泛洪，当网络规模较大时，路由发现和泛洪将占用大量的网络带宽，严重时将导致广播风暴，严重影响传输效率和可靠性。在多障碍、低速网络环境中，数据的可达性更无法保证。

1.2 基于地理位置的路由协议GPSR

GPSR（Greedy Perimeter Stateless Routing）算法是哈佛大学的Brad Karp和H·T·Kung[7]于2000年提出的适用于无线数据包网络的基于地理位置的路由算法。节点通过GPS等定位技术获取本机节点的位置信息，并定期与邻居节点之间相互发送信标消息获取邻居节点的位置。通过贪婪转发算法，选择邻居节点中距离目的节点最近的节点作为下一跳的转发节点。当出现空洞时，GPSR算法由贪婪转发模式进入到周边转发模式。此种算法的主要缺陷在于仅仅通过位置进行路由选择，将会使得某些节点被频繁选中，导致节点易失效。并且，周边转发需要消耗大量网络带宽进行反复修正。在大型建筑物内部环境中，由于GPS定位受到障碍物的干扰，位置定位将会不准确，且建筑物内部环境复杂，信号的传输易受到障碍物的干扰，导致信标信号交换不成功，周期性地与邻居节点交换信标信息也会占用大量的网络带宽，导致不必要的通信开销。这种算法不适合用在障碍物较多的大型建筑物内部环境中。

为了解决上述问题，使得组网算法能够适应多障碍、低速网络环境，本文算法借鉴基于地理位置的路由算法，应用于楼宇供暖数据采集等无线抄表系统，为保证数据的可达性，提供一种高效的数据传输方法。

（1）信号可达性。为提高信号可达性，增强信号的衍射和穿透能力，本文采用较低的传输速度，节点间的传输速度低于9 600bps，同时，采用节点间的信号强度RSSI作为下一跳选择的主要依据，结合实际环境中信号的传输距离与最优半径通信，选择一个最优链路状况的节点作为下一跳路由节点，以此提高信号可达性。

（2）算法扩展性和鲁棒性。相邻节点之间，通过交换hello数据包，确定节点间的连通关系，并将所有节点的连通情况上传至汇集节点，根据节点间的信号强度及连通情况，构建相应的虚拟网络，一旦节点加入或退出，汇集节点可以重新构建虚拟网络，因此可以提高该路由算法的可扩展性和鲁棒性。

（3）采集周期。由于采用较低的传输速度，虽然尽可能地保证信号的可达性，但低传输速度导致采集周期大大加长，本文采用渐进式路由探测方式，利用节点之间的位置进行方向确认，使得每一跳路由的选择都接近于汇集节点与目的节点的连线[8]，减少信号的传输次数和传输距离。同时，将虚拟网络划分成不同的簇，簇內节点通过交换信号强度以及距离汇聚节点的距离，产生新的簇头作为簇中心。由于本文不需要考虑能量问题，因此当且仅当簇头节点不可达时，由汇集节点重新指派新的簇头节点，可以减少簇内节点的选举和成簇带来的带宽消耗。数据采集也由正向采集变为逆向采集，从最大簇头节点开始进行采集数据回传，并在回传路径上采集的簇内节点数据，簇内数据经过簇头节点压缩处理，减少数据通信量，提高链路传输效率。endprint

2 算法描述

2.1 信号衰减模型

无线电波在空气中的衍射和绕透能力决定了信号的可达程度，衍射和绕射能力主要受波长的影响，波长越长，则衍射能力就越强，相应的频率就越低。无线电波在空气中的传输速率c、频率f和波长λ之间的关系如式（1）所示：

λ=cf（1）

同时，无线电波在空气中的传输损耗可由式（2）计算得出：

Los=32.44+20lgd+20lgf（2）

式（2）中，Los为信号在空气中传播的损耗，单位为dB，d为实际σdB（dB）传输距离，f是频率。由式（1）、（2）可得，无线电波在空气中的传输损耗与频率成正比，即信号的传输频率越高，损耗越大，相应的传输距离就会越短。因此，在楼宇等大型建筑物内部的复杂环境中，由于节点部署较为分散且传输过程中需要穿透或绕过大量的墙壁或门窗等障碍物，通常会选用较低的频率来提高信号的传输距离和信号的衍射、绕射能力。

无线电波在传输过程中普遍采用衰减模型——Shadowing模型[9-10]，该模型如下：

P=P0+10nlgdd0+ξ（3）

式（3）中，d0为参考距离，P0为距离d0时接收到的信号强度，其中包含了遮蔽外衰减或环境造成的损耗参考；d为实际距离；ξ为以dB为单位的遮蔽因子，其均值为0，均方差σdB（dB）为正态随机变量；P为正在接收的信号强度；n为路径损耗指数，依赖于环境和建筑物的类型。在实际测量过程中，节点接收到的信号强度符合以下模型，如式（4）所示：

RSSI=-（10nlgd+A）（4）

由于RSSI值受周围环境的影响较大，具有时变特性，会偏离式（4）给出的模型，导致距离估算误差较大。因此采用环境衰减因素模型[11]，如式（5）所示：

RSSI=-（10nlgd+A）-EAF（5）

式（5）中，EAF（dBm）为环境影响因素，取决于室内环境，由实测值RSSI和理想RSSI值计算而来。RSSI为接收到的信号强度，d为实际的传输距离，A为距发射节点1m处的信号强度；n为信号传输常数，与周围环境相关。n和A在不同环境下的取值在文献[10]中给出了如表1所示的数据。

EQi=Weightvw（i）+Weightr（i）（9）

式（9）中，EQi表示第i个候选节点Ki到源节点的链路评估质量，Weightvw（i）表示候选节点Ki在虚拟网络中LQ的权值，Weightr（i）表示候选节点Ki在实际传输环境中的权值，Weightvw（i）、Weightr（i）表示如式（10）、（11）所示：

Weightvw（i）=LQi*lg（Δ）lgd（S，D） LQi>LQThreshold（10）

其中，

Δ=d（S，Ki）*cosSKi，SDWeightr（i）=LQi*lgDi∑ni=0Di LQi>LQThreshold（11）

式（10）中，LQi为第i个候选节点Ki的链路质量，d（S，Ki）为发送节点S与第i个候选节点在虚拟网络中的曼哈顿距离，cosSKi，SD为发送节点、候选节点和目的节点之间的夹角余弦，LQThreshold表示链路质量阈值，通常由实际环境决定。通过计算出候选节点在虚拟网络中的权值Weightvw（i），可以得到在虚拟网络中的最优下一跳节点。式（11）中，Di表示节点在实际环境的通信距离，根据文献[10]中提供的测量结果以及现场实际环境中的测量结果，假定接收信号强度Rssireceive在-55 dB范围内表示最优，-55dB～-65 dB范围内表示次优，超过-70 dB的权值表示信号差，不作为下一跳候选节点，因此由式（5）可以计算出Di。

由式（9）～（11）可以计算出第i个候选节点的链路评估质量EQi，构成EQ集合，并选择最大值Max{EQ1，EQ2，...，EQi，..EQn} ，n表示候选节点个数。由此可以挑选出最优下一跳节点，既满足跳数较少又满足信号可达，在充分保证可达性的前提下缩短时间。

3 算法实现

本算法实现过程主要包含3部分：构建虚拟网络并分簇、选择最优下一跳、数据采集。

3.1 虚拟网络构建及分簇

虚拟网络是由节点相互交换信标信息，确认节点间的相互关系，并通过轉发将消息上传至汇集节点，由汇集节点根据基于三角形的位置估算法TBLA[12-13]确定节点位置后生成的网络拓扑。

虚拟网络构建步骤如下：①固定汇集节点位置和1个与汇集节点相通的邻居节点，并测量两节点的距离，将这两个节点作为定位锚节点；②节点上电后开始发送hello数据包，附近可达节点收到hello数据包后，返回接收到的RSSI值，为了尽可能多地连通邻居节点，每个节点发送3次hello数据包；

③汇集节点发出回收命令，与汇集节点连通的邻居节点广播自己的地址，其它节点收到该节点的广播数据包，将本机节点与邻居节点的连通情况上传给汇集节点；④汇集节点将本机节点与预设的邻居节点作为锚节点，从所有节点中挑选与锚节点相连通的节点，并按照三角形定位算法进行定位，将已经定位的节点设置为新的锚节点。如果某个节点的连通节点中，有大于2个锚节点，则任意挑选两个锚节点进行定位。最终将所有节点与锚节点的距离转换成距汇集节点的距离，构建虚拟网络；⑤虚拟网络构建完成后，按照节点间的连通关系，根据节点间两两可达关系划分成多个簇，如果某节点只与一个节点相连，则将该节点划分到该簇。

图1显示了节点在实际环境中的安装位置，每个网格代表一间房间，汇集节点位置固定，R为节点的最大通信半径，由汇集节点和锚节点对其它节点进行定位。如图2所示，节点1经过定位，由（1，3）位置变为（1，2），节点0由（1，1）变为（2，1），说明通过汇集节点与锚节点0定位时，节点1与汇集节点间的RSSI比节点1与锚点0的RSSI要强，因此，节点1更靠近汇集节点。同时，将已经定位的节点1设置为新的锚节点。endprint

3.2 选择最优下一跳

最优下一跳的选择主要依据链路评估质量EQ进行选择，如图3所示。

图3中，S表示源节点，D表示目的节点，K1和K2表示在候选区间内的下一跳候选节点，候选区域一般选择源节点与目的节点方向上90°范围，具体算法如下：

1：if 目的节点是源节点的邻可达邻居节点 then

2： do 直接发送转发包

3：else 根据源节点与目的节点的方向，选择前进方向90°范围作为候选节点，并向候选区域内的节点，发送链路探测帧，并开启定时器等待数据回收

4：end if

5： if 定时器时间到 then

6： do 处理链路探测回复帧

7： if 回复节点数量Count > 0 then

8： do 计算链路评估质量EQ，并选择最优下一跳，向下一跳节点发送链路驱动数据帧。

9： else 对探测帧进行重传，重新启动定时器

10： end if

11：else 接收来自节点的链路探测回复帧

12：end if

通过上述算法，可以在候选区域内挑选出一个最优候选节点作为下一跳节点，并按照链路驱动数据帧中的指示进行下一步探测转发过程，链路探测帧中包含该节点下一跳所需探测的节点列表。

3.3 数据采集

为加快数据采集速度，减少采集周期，本文采用分簇的方式，由簇头节点定期采集簇内节点保存的数据。按照数据逆向采集方式，从距离汇集节点最远的簇开始进行数据采集，同时在数据回传过程中，采集回传路径上簇内节点的数据。由于一次传输的字节数有限，可通过差值法对数据进行简单压缩，减少字节传输量。

4 结语

本文提出一种面向位置信息的路由算法，该算法主要适用于大型建筑内部的无线网络互联，选用较低频率提高信号的绕射能力并加长传输距离，以此提高信号的可达性，保证数据的交付。该算法具有良好的稳定性和可扩展性，适合在无线抄表、楼宇供暖等节点易失效、信息采集不全的工程中使用，因此该算法在多障碍、低速无线自组网中具有很高的应用价值。

参考文献：

[1] CADGER F，CURRAN K，SANTOS J，et al.A survey of geographical routing in wireless Ad-hoc networks[J].IEEE Communications Surveys & Tutorials，2013，15（2）：621-653.

[2] YIN XIUYAN，HOU ENZU，ZOU WENQI.The application of GPRS based communication technology in remote meter reading[Z].Relay，2006.

[3] YAN YINFA，GONG MAOFA，TANG YUANXIN.The design of zigbee based wireless network meter reading system[J].Electrical Measurement &Instrumentation，2006，43（6）：1-5.

[4] YANG F，QIU K，NIU T，et al.A low-cost and low-power wireless automatic meter reading node network routing algorithm[C].IEEE International Conference on Software Engineering and Service Science，2014：1072-1075.

[5] WANG G，QIU K，NIU T，et al.The design and implementation of an ad hoc-based wireless meter reading system[C].IEEE International Conference on Software Engineering and Service Science，2013：565-569.

[6] PERKINS B C，ROYER E.Ad hoc on demand distance vector （AODV） routing[C].Proceedings of IEEE Workshop on Mobile Computing Systems and Applications，New，2010.

[7] KARP B.Greedy perimeter stateless routing for wireless networks[Z].2010.

[8] BANERJEE I，ROY I，CHOUDHURY A R，et al.Shortest path based geographical routing algorithm in wireless sensor network[C].International Conference on Communications，Devices and Intelligent Systems，2012：262-265.

[9] AWAD A，FRUNZKE T，DRESSLER F.Adaptive distance estimation and localization in WSN using RSSI measures[C].Euromicro Conference on Digital System Design Architectures，Methods and Tools，2007：471-478.

[10] ZHU MING-HUI，ZHANG HUI-QING.Research on model of indoor distance measurement based on RSSI[J].Transducer and Micorsystem Technologies，2010，29（8）：19-22.

[11] 朱明輝，张会清.基于RSSI的室内测距模型的研究[J].传感器与微系统，2010，29（8）：19-22.

[12] 石为人，熊志广，许磊.一种用于室内人员定位的RSSI定位算法[J].计算机工程与应用，2010，46（17）：232-235.

[13] 万国峰，钟俊.基于三角形理论的无线传感器网络定位算法[J].计算机应用研究，2013，30（1）：249-251.endprint