利用信号强度的桥梁健康监测传感网的节点次序自动推导方法

摘要

本发明公开了一种利用信号强度的桥梁健康监测传感网的节点次序自动推导方法，包括以下步骤：(1)启动，汇聚节点发出启动指令到桥梁健康监测传感网网络中，节点次序自动推导方法启动；(2)数据收集，传感器节点在收到指令后自由广播报文，同时监听其他节点的信号，记录信号强度，将收集到的信号强度数据返回给汇聚节点；(3)数据整理，汇聚节点将收集到的信号强度数据根据发射节点和数据包的编号整理，剔除不完整数据；(4)自动排序，汇聚节点对每一组整理过的数据执行提出的排序算法，给出节点相对次序；(5)结束，当连续多次得到同样的相对次序时，汇聚节点输出排序结果，并发出终止指令到网络中，传感器节点停止广播报文和收集数据。

说明书

一、技术领域

本发明对布置在桥梁上的具有线性拓扑结构的传感器网络提出了一种实用的节点次 序推导方法，它能够在不增加额外硬件、不影响网络正常工作、只需在节点端添加少量 代码的情况下，自动推导出节点相对次序。本发明同样适用于布置在道路、直树等其他 具有线性拓扑结构的传感器网络。

二、背景技术

使用传感器网络进行桥梁健康监测、路况监控、直树的生态数据采集等是传感网的 典型应用，在这些场景下传感节点呈现一维布局，或是线性拓扑，我们称这类网络为“线 性传感网”。在线性传感网中，节点的次序指的是节点在物理空间上的排序，例如，节 点次序为2-1-3-4指的是，节点2和4位于网络的边缘，节点1位于节点2和3之间， 节点3位于节点1和4之间。线性传感网中节点次序对节点的定位、地理位置信息路由、 节点编号检错具有重要价值。以节点编号检错为例。当前市面上的传感器节点在出产时 并没有类似MAC地址等的唯一标识，在应用中节点的编号信息全部由程序设置或由程序 员手工输入，当节点个数较多或是系统运行中软件更新换代时，极易出现节点编号与原 先设计不一致的情况。我们考虑如何在不影响系统正常工作、无需为节点添加额外硬件 的前提下，自动推断出节点间的相对次序，从而能够以极低的开销检测出节点编号与设 计不匹配的情况。研究的关键是如何在满足以上要求的前提下保证方法的正确率。

目前，未见推导节点次序的实用方法。

三、发明内容

本发明目的是：提出一种能够在布置于桥梁的线性传感网中快速找到节点相对次序 的方法，能够以只更新少量节点程序的形式直接应用到已布置的线性传感网系统中，且 具有开销低、正确率高的特点。

为实现上述目的，本发明的技术方案是：利用信号强度的桥梁健康监测传感网的节 点次序自动推导方法，包括以下步骤：

(1)启动，汇聚节点发出启动指令到桥梁健康监测传感网网络中，节点次序自动推 导方法启动；

(2)数据收集，传感器节点在收到指令后自由广播报文，同时监听其他节点的信号， 记录信号强度，将收集到的信号强度数据返回给汇聚节点；

(3)数据整理，汇聚节点将收集到的信号强度数据根据发射节点和数据包的编号整 理，剔除不完整数据；

(4)自动排序，汇聚节点对每一组整理过的数据执行提出的排序算法，给出节点相 对次序；

(5)结束，当连续多次得到同样的相对次序时，汇聚节点输出排序结果，并发出终 止指令到网络中，传感器节点停止广播报文和收集数据。

进一步，步骤(2)中让每个节点纯分布式地广播数据，从而降低了系统的部署成本；

步骤(2)数据收集中，在传感器节点刚被布置到实际环境中，或是有新的节点加入， 或是部分传感器节点由于损坏而被替换，或是软件在更新过程中改变节点的编号时，汇 聚节点广播一个特殊的启动报文，该报文通过单跳或多跳的方式到达每个传感器节点；

每个传感器节点在收到此指令后，独立地、周期性地广播一种称为“短消息” 的报文；短消息报文包含以下两个字段：发送者编号SenderID，消息序号MsgSeq；每 个传感器发送编号是在将操作系统安装到传感器节点时为其设置的唯一代码，在TinyOS 操作系统下为TOS_NODE_ID的值；消息序号为一个16比特长的无符号数字，从0开始 计数，每次发送一个广播报文后均执行加1操作，溢出时重新从0开始计数，因此由同 一个发送者发出的两个相邻短消息的序号相差1；因为只包含这两个字段，因此命名此 类报文为“短”消息；报文变短能减小干扰；

步骤(3)数据整理，汇聚节点持续不断地收到来自传感器节点的汇报数据，并实时执 行数据整理操作。数据整理的任务是将“不合格”(即，不满足最强信号对应最短距离 这个观测规律)的数据剔除出去，并将数据组织成利于后续算法开展的格式；汇聚节点 在本地维护两种缓存池，大小不一；较大的命名为临时缓存，较小的命名为样本缓存； 临时缓存会存储所有的RSSI数据，当临时缓存溢出时，溢出的数据被输出到样本缓存 中，当样本缓存同样被填满时，在经过检测后便输出最终合格的数据；临时缓存为每个 信号发射节点SenderID维护一个缓存，缓存的每一个条目对应于SenderID的某一个短 消息，即，对应于某一个MsgSeq；

步骤(3)数据整理时剔除不完整数据，从而解决了由纯分布式特征而造成的可能的信 号冲突和丢失。

步骤(4)中提出了一个高效的节点次序推导算法，它利用了节点信号强度与距离的关 系，通过对线性网络端节点的枚举而寻找到整个网络节点的次序；算法在汇聚节点处执 行，利用了汇聚节点计算能力较强的特性从而避免给计算能力较弱的普通传感器节点增 加额外计算开销。

自动排序，排序算法的依据是：从某个节点的某一侧来看，距其最近的节点观测到 的RSSI最大；因此，测试一个节点是否能为端节点，若它是端节点，则从它的样本缓 存中能够找到离它最近的节点，即RSSI最强的节点；将端节点删除后，刚找到的节点 便成为剩余网络的新的端节点，以此类推；若此流程将所有节点均删除，则原先的待测 试节点可能是端节点，而节点被删除的顺序便成为一个备选次序；此时，测试备选次序 的最后一个节点能否是端节点，若答案是肯定的，并且两个得出的次序互为倒置，则得 到一个正确的节点次序；当对所有的节点进行端节点测试后，若得到了0个或两个以上 的正确次序，则定位失败；否则，若仅得到了一个正确的次序，则定位成功，输出此次 序；

由于传感器节点在收到终止指令前不断收集RSSI并汇报给汇聚节点，因此，汇聚节 点的样本缓存不停被填满，从而引起算法3的执行，若连续多次算法3的输出均一致，则 正确的次序已经找到；此时，由汇聚节点发出一个终止指令到传感网中，传感器节点停 止收集和汇报数据。

本发明的有益效果：该方法在数据收集时不需要节点之间进行协调，是完全分布式 的，避免了因为节点协调而带来的额外开销，而由此造成的不完整数据在数据整理阶段 被自动剔除；汇聚节点用于排序传感网节点的算法具有极低的时间开销和极高的准确率， 非常适用于桥梁健康监测传感网以及其他大规模线性传感网。本发明能对布置在桥梁上 的传感网在不使用额外硬件的前提下快速推导节点次序的方法，当连续多次得到同样的 相对次序时，汇聚节点输出排序结果，并发出终止指令到网络中，传感器节点停止广播 报文和收集数据。

四、附图说明

图1为本发明短消息报文格式；

图2为汇总报文的格式；

图3为临时缓存的组织形式；

图4为样本缓存的组织形式。

五、具体实施方式

本发明可分为3个阶段：数据收集、数据整理、自动排序。

阶段1：数据收集

在传感器节点刚被布置到实际环境中，或是有新的节点加入，或是部分传感器 节点由于损坏而被替换，或是软件在更新过程中有可能改变节点的编号时，管理者有必 要担心是否出现节点编号与预先安排不一致的情况，此时，管理者可令汇聚节点发起本 方法。为此，汇聚节点广播一个特殊的启动报文，该报文通过单跳或多跳的方式到达每 一个传感器节点。

传感器节点在收到此指令后，独立地、周期性地广播一种称为“短消息”的报 文。短消息报文包含以下两个字段：发送者编号SenderID，消息序号MsgSeq，如图1所 示。发送者编号是在将操作系统安装到传感器节点时为其设置的唯一代码，在TinyOS操 作系统下为TOS_NODE_ID的值；消息序号为一个16比特长的无符号数字，从0开始计数， 每次发送一个广播报文后均执行加1操作，溢出时重新从0开始计数，因此由同一个发送 者发出的两个相邻短消息的序号相差1。因为只包含这两个字段，因此命名此类报文为 “短”消息。报文变短可以减小干扰的影响。为每个消息设置一个序号是为了保证其他 节点测得的信号强度是来自同一个短消息，即，同一次信号发送。虽然消息序号可能溢 出的情况会导致来自同一个发送者的两个不同消息具有相同的消息序号，但是因为序号 是16比特数据，有65536种，当溢出时，网络中其他节点收到的前一轮报文的信息已经 被清除，所以在实际中未观测到由此造成的负面影响。

见图1短消息报文的格式。传感器节点在广播自己消息之余监听来自其他节点的短 消息报文，每次收到一个短消息报文，便在本地记录以下三个数据，称为“三元组”： 发送者编号SenderID，消息序号MsgSeq，信号强度RSSI。其中，发送者编号和消息序号 直接从收到的短消息中读取，信号强度是从节点本地的无线电模块处取得。当此类三元 组的个数达到一定阈值时(由单个报文的最大长度决定)，便将本地缓存的数据通过单 跳或多跳发送给汇聚节点。此类“汇总报文”具有以下格式，如图2汇总报文的格式所 示：

(ObserverID，三元组1，三元组2，三元组3，...)

其中，ObserverID即为汇报数据的节点的编号，起名为Observer意指它是信号的观 测者。考虑到汇报报文有可能丢失，每个三元组只有在被汇报两次后才从本地缓存中清 除，具体的操作如下。假设单个报文最多能够容纳的三元组个数为N，节点持续不断地 采集到了以下编号的三元组

1,2,3,4，...,N-1,N,N+1,...,

则节点第一次汇报前N/2个三元组，分别为1,2，...,N/2。自此后每次汇报N个三 元组，即，第二次汇报1,2,...,N，第三次汇报N/2+1,...,3N/2,第四次汇报N+1,..., 2N，等。每个三元组在被汇报两次后便从本地缓存中清除，为后续的三元组让出空间。 因此，传感器节点本地缓存的大小只需为N个三元组的长度，即为一个报文的大小。

阶段2：数据整理。

汇聚节点持续不断地收到来自传感器节点的汇报数据，并实时执行数据整理操作。 数据整理的任务是将“不合格”(随后定义)的数据剔除出去，并将数据组织成利于后续 算法开展的格式。具体操作如下。

汇聚节点(一般为电脑)在本地维护两种缓存池，大小不一。较大的命名为临时缓 存(如图3所示)，较小的命名为样本缓存(如图4所示)。临时缓存会存储所有的RSSI数 据，当临时缓存溢出时，溢出的数据被输出到样本缓存中，当样本缓存同样被填满时， 在经过检测后便输出最终合格的数据。

临时缓存为每个信号发射节点SenderID维护一个缓存，缓存的每一个条目对应于 SenderID的某一个短消息，即，对应于某一个MsgSeq。缓存条目的内容是其他节点观测 到的RSSI，即，每一个条目的内容形如

MsgSeq,(ObserverID,RSSI),(ObserverID,RSSI),...,(ObserverID,RSSI)；

当汇聚节点接收到一个汇总报文时，便将其中的数据取出，分别插入到各个发射节 点的临时缓存中，若发现对应位置已经有数据(有可能出现，因为每一组RSSI数据将会 被汇报两次)，则忽略。对于任意一个发射节点，若它的临时缓存中尚未包含有同样 MsgSeq的短消息，并且缓存已满(已经存入的条目数达到了允许的最大值)，则将时间 最老的那个缓存条目输出到样本缓存池中，并将其从临时缓存中删除以存储后续的数据。

图3临时缓存的组织形式：样本缓存中，每个发射节点拥有一个仅能容纳一个条目 的空间，用于放置临时缓存输出的条目。由临时缓存输出的每个条目，如果在样本缓存 中没有放置空间(对应位置已经有条目)，则将样本缓存中对应的条目替换。当所有发 射节点的位置均包含有一个条目时(即样本缓存已被填满)，程序检测样本缓存中的数据 是否能够构成一个强连通图(算法1)，若可以，则将样本缓存的数据输出，用于后续的 次序推导算法。无论是否可以，在执行完检测连通性操作后，样本缓存被清空。见图4 样本缓存的组织形式。

算法1数据完整性检测算法

使用双缓存的原因是，它可以高效地解决数据延迟引起的问题。注意，不同传感器 节点发送的汇总报文到达汇聚节点所使用的时间可能是不同的，因此我们需要等待最慢 的节点发送的汇总报文。但我们却无法知道汇总报文究竟是被延迟了，还是在传输过程 中丢失了。解决此问题的一般方法是使用计时器，但为每个传感器节点维护一个计时器 将会增加程序的复杂度。为此，我们提出了上述双缓存结构，当某个节点的临时缓存被 填满时，我们便认为临时缓存中最早的数据已经全部到达了，从而将对应的条目从临时 缓存中删除，并输出到样本缓存中。如此操作相当于为每个传感器设置了一个计时器， 但操作起来比传统的计时器更加容易。

我们对样本数据进行连通性检测的原因是，实际中的网络需要经常性地收集数据， 因此网络一定是强连通的，即，任意两个节点之间均可以通过单跳或多跳的路径进行通 信。所以，我们观测到的样本数据必然会产生一个强连通图。倘若样本缓存中的数据不 能对应一个强连通的网路，那么，汇总报文或者短消息的发送过程中一定出现了异常， 可能的异常原因包括数据包冲突，外界的无线电干扰，障碍物的出现。因为这部分样本 数据是异常的，不适合用于后续的次序推导方法，所以我们直接剔除这部分数据。

阶段3：自动排序

上一阶段输出的样本缓存如图4所示。我们排序算法的依据是：从某个节点的某一侧 来看，距其最近的节点观测到的RSSI最大。例如，倘若节点的真实次序是32145， 则，我们应当能够观测到如下现象：节点3的样本缓存中必包含节点2，并且，节点2对 应的RSSI应当是节点3的样本缓存中最强的；节点2的样本缓存中必包含节点3和节点1， 并且，节点1对应的RSSI应当比节点4、5要强；节点1的样本缓存中必包含节点2和节点4， 并且，节点2对应的RSSI应当比节点3强，节点4对应的RSSI应当比节点5强，等等。

因此，算法的基本思想是，测试一个节点是否可以是端节点。若它是端节点，则我 们从它的样本缓存中能够找到离它最近的节点，即RSSI最强的节点；将端节点删除后， 刚找到的节点便成为剩余网络的新的端节点，以此类推。若此流程可以将所有节点均删 除，则原先的待测试节点可能是端节点，而节点被删除的顺序便成为一个备选次序，如 算法2所示。此时，测试备选次序的最后一个节点能否是端节点，若答案是肯定的，并 且两个得出的次序互为倒置(如，一个是123，一个是321)，则我们得到一个正确 的节点次序。当对所有的节点进行端节点测试后，若我们得到了0个或两个以上(包含) 的正确次序，则定位失败。否则，若仅得到了一个正确的次序，则定位成功，输出此次 序，如算法3所示。

由于传感器节点在收到终止指令前不断收集RSSI并汇报给汇聚节点，因此，汇聚节 点的样本缓存不停被填满，从而引起算法3的执行，若连续多次算法3的输出均一致，则 正确的次序已经找到。此时，由汇聚节点发出一个终止指令到传感网中，传感器节点停 止收集和汇报数据。

算法2端节点验证算法

算法3节点排序算法