一种传感器网络骨架提取方法

摘要

本发明公布了一种传感器网络骨架提取方法，包括以下步骤：1、找出边界上的角点，将边界被划分为有限个边界分支；2、识别出相互连通的骨架节点；3、在连通的骨架节点中搜索最远距离的两骨架节点，连接这两个骨架节点生成骨架弦；4、连接相邻骨架弦，再将角点与最近骨架弦相连，生成粗糙骨架图；5、采用剪枝方法优化粗糙骨架图，得到最终骨架。本发明利用不同边界分支确定骨架节点，与传统的算法相比，不会受到边界扰动影响，因而能得到更加近似的网络拓扑结构，从而更好的重构网络。

权利要求

1.一种传感器网络骨架提取方法，包括以下步骤：

1)根据节点曲率与预定曲率阈值的比较结果确定网络边界上的节点哪些为角点，相邻两个角点之间的边界节点组成边界分支{Cn，n＝1，…，P}，P为角点数；

2)搜索到最近两个边界分支Ci，Cj的距离之差的绝对值小于等于预定修正量σp的节点，称其为骨架节点，边界分支Ci，Cj对应的骨架节点形成连通分量，Ci，Cj∈{Cn，n＝1，…，P}；

3)在每一连通分量中，搜索具有最长连通路径的两个骨架节点，这两个骨架节点以及它们之间最长连通路径上的所有节点构成骨架弦；

4)相邻的骨架弦端点节点通过广播方式相连，再将各角点与其最近的骨架弦端点节点相连，生成粗糙骨架；

5)采用广播方式找到并删除粗糙骨架上没有子节点且不是角点的骨架节点，得到最终网络骨架。

2.根据权利要求1所述的一种传感器网络骨架提取方法，其特征在于，若连通分量中存在聚合节点，则该连通分量的骨架弦的一个端点必为聚合节点，所述聚合节点指到三个或三个以上最近的边界分支中，到其中任意两个边界分支的距离之差的绝对值均小于等于修正量σp的骨架节点。

3.根据权利要求1或2所述的一种传感器网络骨架提取方法，其特征在于，所述修正量σp取值范围为0＜σp＜d(Ci，Cj)，d(Ci，Cj)表示边界分支Ci与Cj间的节点距离最大值。

说明书

一种传感器网络骨架提取方法

技术领域

[0001] 本发明涉及无线传感器网络技术领域，特别是涉及基于连接信息的网络骨架提取方法。

背景技术

[0002] 许多传感器网络装置与传感器节点所处的集合环境紧密相关，关于传感器网络拓扑的骨架抽取大大地提高了传感器网络中诸如定位、路由选择等服务的性能。在计算机视觉研究领域中，关于拓扑抽取的研究主要集中在连续空间上，不能直接应用到离散的传感器网络上。在现有关于拓扑发现的文献中，主要集中于边界识别技术，以及在此基础上找出骨架线。其中具有代表性的是JehoshuaBruck等提出的MAP算法，具体做法是：先识别出传感器网络的边界，再利用最大内切圆方法，去判定一个节点是否为中轴节点。若某节点的最大内切圆与边界有两个交点，则该节点即被当作中轴节点。由于传感器网络节点是离散分布，这种方法往往会容易受到边界扰动的影响，得到不真实的中轴节点，以致中轴线不能很好的代表传感器网络的真实拓扑结构。

发明内容

[0003] 针对现有方法的不足，本发明提出了一种网络骨架提取方法，该方法不会受到边界扰动影响，能得到更加近似的网络拓扑结构。

[0004] 一种传感器网络骨架提取方法，包括以下步骤：

[0005] 1)根据节点曲率与预定曲率阈值的比较结果确定网络边界上的节点哪些为角点，相邻两个角点之间的边界节点组成边界分支{Cn，n＝1，…，P}，P为角点数；

[0006] 2)搜索到最近两个边界分支Ci，Cj的距离之差的绝对值小于等于预定修正量σp的节点，称其为骨架节点，边界分支Ci，Cj对应的骨架节点形成连通分量，Ci，Cj∈{Cn，n＝1，…，P}；

[0007] 3)在每一连通分量中，搜索具有最长连通路径的两个骨架节点，这两个骨架节点以及它们之间最长连通路径上的所有节点构成骨架弦；

[0008] 4)相邻的骨架弦端点节点通过广播方式相连，再将各角点与其最近的骨架弦端点节点相连，生成粗糙骨架；

[0009] 5)采用信息广播方式找到并删除粗糙骨架上没有子节点且不是角点的骨架节点，得到最终网络骨架。

[0010] 作为本发明的改进，若连通分量中存在聚合节点，则该连通分量的骨架弦的一个端点必为聚合节点，所述聚合节点指到三个或三个以上最近的边界分支中，到其中任意两个边界分支的距离之差的绝对值均小于等于修正量σp的骨架节点。

[0011] 所述修正量σp取值范围为0＜σp＜d(Ci，Cj)，d(Ci，Cj)表示边界分支Ci与Cj间的节点距离最大值。

[0012] 本发明的技术效果体现在：

[0013] 本发明从任意一个角点开始，沿着粗糙的骨架广播，剔除没有子节点且非角点的节点，形成优化骨架，其优点在于不会形成类似环状之类的情况。同时，集中式的全局算法并不适合传感器网络这样的分布式网络，应该设计一个全局算法的分布式近似方法，在基本保留全局算法的优越性的同时获得分布式的特性。由于CASE算法为分布式而非集中式算法，它是全局算法的分布式实现，因此该算法适合应用于具有分布式特点的传感器网络；该算法无论是时间复杂度还是空间复杂度，均与网络节点数成线性关系，因此，提取骨架需要的数据包和网络延迟不会因为传感器网络的节点数增加而影响性能，因而具有良好的可扩展性；同时，该算法利用不同边界分支来确定骨架节点，与传统的算法相比，不会受到边界扰动影响，因而能得到更加近似的网络拓扑结构，从而更好的重构网络。

附图说明

[0014] 图1是本发明方法流程示意图；

[0015] 图2是本发明识别骨架节点步骤的流程示意图；

[0016] 图3是本发明的传感器网络模型示例图；

[0017] 图4是本发明边界划分示例示意图；

[0018] 图5是本发明传感器网络的骨架节点和聚合点示意图；

[0019] 图6是本发明传感器网络的骨架弦示意图；

[0020] 图7是本发明传感器网络的粗糙骨架示意图；

[0021] 图8是本发明取δp＝0.50的传感器网络骨架示意图；

[0022] 图9是本发明取δp＝0.75的传感器网络骨架示例图；

[0023] 图10是本发明取δp＝0.86的传感器网络骨架示例图。

具体实施方式

[0024] 为了更加清楚的表明本发明，下面结合附图及具体实例详细说明。

[0025] 本发明所应用的传感器网络仅仅利用了传感器间的连接信息，我们利用现有文献中的方法识别出网络边界，因此可以假定传感器网络的边界信息已知。

[0026] 图1是本发明方法流程示意图，包括以下步骤：

[0027] 步骤1.找出网络边界上的角点

[0028] 这一步骤主要是为了将网络的边界划分为有限个边界分支做铺垫。对于任意一个边界上的节点p，记它的所有h跳(h与实际应用及要求有关，一般可取2～5跳)邻居节点集合为Nh(p)，在Nh(p)中两节点之间距离的最大值为Mh(p)，则定义节点p的曲率为：0≤ρp≤1，若ρP的值小于给定的曲率阈值δp(0＜δp＜1)(如取
δp＝0.5)，则节点p为角点。通过设定不同的曲率阈值，可以得到不同的边界分支。曲率阈值越大，被视为角点的节点越多，从而边界分支越多，得到的骨架重构网络精度就越高。

[0029] 图3为实例应用的传感器网络示意图，取δp＝0.5，则获取角点p1，p2，p3，p4，如图4所示。

[0030] 步骤2.边界划分

[0031] 在识别出边界上的角点后，可以利用这些角点来对边界进行划分。任何相邻两个角点之间的边界节点组成一个边界分支。参考图4，p1，p2，p3，p4这四个角点将网络边界划分为p1p2，p2p3，p3p4，p1p4四个部分。

[0032] 步骤3.识别骨架节点

[0033] 本发明中的骨架节点，指满足到最近的两个边界分支(Ci，Cj)的距离之绝对差小于给定修正量σp的节点。修正量σp取值范围为0＜σp＜d(Ci，Cj)，这里d(Ci，Cj)表示边界分支Ci上的节点与边界分支Cj的上节点间距离的最大值。节点到边界分支的距离是指节点与边界分支上节点间的最小距离。如果骨架节点与三个或三个以上最近的边界分支中，节点到任两个边界分支的距离之差的绝对值均小于等于修正量σp，这样的骨架节点被称作聚合点。设Ci和Cj表示两个不同的边界分支，若节点p到边界分支Ci和Cj距离之差的绝对值小于等于给定修正量σp，则节点p称为由边界分支Ci和Cj所对应的骨架节点。如果所有这样的骨架节点组成一个连通分量，则停止识别边界分支Ci和Cj所对应的骨架节点。否则，增大修正量σp(每次加1)，得到更多的骨架节点，直至所有这样的节点组成一个连通分量。

[0034] 设这些节点所组成的连通分量用CC(Ci，Cj)表示。由骨架节点的定义可知，到Ci和Cj距离绝对差小于等于修正量σp的节点都属于CC(Ci，Cj)，而任何属于CC(Ci，Cj)的节点p都可以通过洪泛来检验分量CC(Ci，Cj)是否为连通分量。

[0035] 图2是本发明识别骨架节点步骤的流程示意图。

[0036] 图5中，区域I，II，III，IV和V中的节点表示各连通分量中的骨架节点，区域VI中的节点表示聚合点。

[0037] 步骤4.连接骨架节点，生成骨架弦

[0038] 首先要找出连通分量CC(Ci，Cj)中两节点间的最大距离。对于连通分量CC(Ci，Cj)中每个节点p，在向其他节点发起洪泛时，数据包里的信息为发送节点ID和数据包传输所经过的节点数目的计数器。节点p的邻居节点中，所有到Ci和Cj的距离之绝对差小于修正量σp的节点，都会转发来自p的数据包，同时增加计数器的值，并记录下两个节点之间路径；若p的邻居节点不是骨架节点，则该邻居节点不再转发数据包。通过这样的方式，可以找出CC(Ci，Cj)连通分量中两节点间的最远距离，其对应的两个节点生成一条最长路径，最长路径上的所有节点构成连通分量CC(Ci，Cj)中的骨架弦。

[0039] 若有多条路径且有聚合节点存在，则应选择端点为聚合节点的最长路径。

[0040] 图6是本专利示例所用的传感器网络区域中的骨架弦。

[0041] 步骤5.连接各骨架弦和角点，生成粗糙骨架图

[0042] 步骤51：各骨架弦的端点以类似星型树的方式广播，并记录传送路径，从而将所有相邻骨架弦连接起来；

[0043] 步骤52：每个角点通过洪泛，寻找到骨架弦的最短路径，从而得到粗糙的骨架图。

[0044] 图7是本发明示例的传感器网络的粗糙骨架。

[0045] 步骤6.采用剪枝优化粗糙骨架图，得到最终的骨架图。

[0046] 任选一个角点cp，沿粗糙的骨架做限制性广播，即只有粗糙骨架上的节点q才会转发(从父节点处)接收到的数据包。如果邻居骨架节点p已经收到信息，则不再转发，否则节点q将收到的数据包，沿着粗糙骨架转发它所接收到的数据包，直到粗糙骨架上的所有节点都收到了来自角点cp的数据包。然后，通过剪枝，删除粗糙骨架上的度为1(即没有子节点)且不是角点的骨架节点，并将余下节点与其父节点相连，可得到优化的骨架图。父节点和子节点的含义为：粗糙骨架上的节点P1将信息传送给节点P2，节点P2将信息传送给P3，则节点P1为P2的父节点，P3为P2的子节点。

[0047] 图8是δp＝0.50时示例的传感器网络优化骨架示意图，图9和图10是分别取δp＝0.75和δp＝0.86时示例的传感器网络优化骨架示意图，可以看出，δp越大，得到的骨架就越接近真实。