PatViewer专利搜索

一种成本有效的视频传感器网络覆盖增强的实现方法

发明公布  无效
申请(专利)号:CN200710063402.6国省代码:北京 11
申请(专利权)人:北京邮电大学
温馨提示:Ctrl+D 请注意收藏,详细著录项请首页检索查看。 Please note the collection. For details, please search the home page.

摘要:
一种成本有效的视频传感器网络覆盖增强的实现方法,操作步骤为:(1)部署阶段:根据实际监测需求,估算所需部署的视频传感器节点数目,并随机部署在目标区域内;其中所有视频传感器节点均同构,且各视频传感器节点一经部署位置固定不变,但都可调整各自传感方向;(2)调整阶段:在视频传感器节点位置固定的情况下,调整各视频传感器节点的传感方向,消除视频传感器网络中感知重叠区和盲区,以较小代价增强视频传感器网络对目标区域的覆盖性能。本发明能确定满足实际监测需求的视频传感器网络部署数量,以节约网络成本;通过视频传感器节点传感方向的自调整,以较小代价实现视频传感器网络对监控区域目标探测能力的显著改善。

主权项:
1、一种成本有效的视频传感器网络覆盖增强的实现方法,其特征在于:包括下述两个操作步骤:(1)部署阶段:根据实际监测需求,估算出所需部署的视频传感器节点数目,并采用随机方式部署在目标区域内;该网络中所有视频传感器节点均同构,且所有视频传感器节点一经部署位置固定不变,但都可调整各自的传感方向;(2)调整阶段:在视频传感器节点位置固定的情况下,调整各个视频传感器节点的传感方向,以消除视频传感器网络中感知重叠区和盲区,以较小代价增强视频传感器网络对目标区域的覆盖性能。


相似专利
随机 阶段 重叠区 部署阶段 部署 视频传感器 视频 节点均 自传感 网络部署 网络对 网络 盲区 监测 监控 探测 感知 但都 估算 传感器节点 传感器网络 传感 代价 个视频
一种海洋环境中无线传感网的覆盖方法
基于监测可靠度的直线型带状无线传感器网络部署方法
基于三维感知的无线传感器网络确定性空间部署方法
一种检测与修补无线视频传感器网络最坏情况覆盖的方法
一种面向目标检测的无线传感器网络强栅栏覆盖构建方法
一种面向目标检测的无线传感器网络弱栅栏覆盖构建方法
一种结合能量有效性的传感器网络覆盖空洞检测方法
面向未知环境探测的移动机器人自部署感知网络
基于差分进化的视频传感器网络覆盖增强实现方法
基于差分进化的视频传感器网络覆盖增强实现方法
一种检测与修补无线视频传感器网络最坏情况覆盖的方法
一种结合能量有效性的传感器网络覆盖空洞检测方法
一种有向传感器网络强栅栏覆盖判定方法
基于虚拟势场的视频传感器网络覆盖增强的实现方法
基于虚拟势场的视频传感器网络覆盖增强的实现方法
视频传感器网络对移动目标运动轨迹覆盖增强的实现方法
一种适用于感知方向可调的视频传感器网络区域覆盖优化的方法
基于三维感知的无线传感器网络确定性空间部署方法
一种成本有效的视频传感器网络覆盖增强的实现方法
基于连通度的直线型规则带状无线传感器网络部署方法
说明书

一种成本有效的视频传感器网络覆盖增强的实现方法

技术领域

本发明涉及一种成本有效的视频传感器网络覆盖增强的实现方法,属于无
线自组织网络系统技术领域。

背景技术

随着嵌入式计算技术、传感器技术和无线通信技术的飞速发展和日益成熟,
具有感知能力、计算能力和通信能力的微型传感器开始出现。由这种传感器所
构成的无线传感器网络使逻辑上的信息世界与真实的客观、物理世界紧密结合;
从而真正实现“无处不在的计算”模式。由于无线传感器网络能够获取客观世界
的各种物理信息,可应用于军事国防、工农业控制、生物医疗、环境监测、抢
险救灾、防恐反恐等诸多领域,具有广阔的应用前景。

目前,大部分无线传感器网络的原型系统都是由温度、湿度、光强等具有
采集简单数据能力的传感器节点所构成。然而,环境监测的日趋复杂、多变使
得传统的传感器网络无法满足人们对环境监测的全面需求,迫切需要将信息量
丰富的图像、视频等媒体引入到以传感器网络为基础的环境监测活动中来。由
此,视频传感器网络应运而生。美国加利福尼亚大学、卡耐基梅隆大学等著名
学府率先开展了该领域的理论和应用研究,建设了演示系统。国内的科研院所
(如:中国科学院计算所)和高等院校(如:北京邮电大学、哈尔滨工业大学)
也开展了相关的研究。

覆盖控制是视频传感器网络中的一个基本问题,反映了视频传感器网络所
能提供的“感知”服务质量,可以使视频传感器网络的空间资源得到优化分配,
进而更好地完成环境感知和信息获取的任务。近年来,众多国内外研究学者相
继开展了传感器网络中覆盖控制方面的研究,并取得了一定的进展。但从当前
可获取的资料看,绝大多数覆盖控制的研究都是针对全向感知模型的传感器网
络展开的,即网络中传感器节点的感知范围是一个以节点为圆心,感知距离为
半径的圆形区域。然而,视频传感器网络中视频传感器节点的感知能力受到方
向性限制,即其感知范围是一个以节点为圆心、与感知距离和感知视角相关的
扇形区域。因此,现有的覆盖控制研究成果不能直接用于视频传感器网络。

在《有向传感器网络的覆盖问题研究》(“On Coverage Problems of
Directional Sensor Networks”发表于MSN’05)文章中,作者率先开展视频传感
器网络中覆盖完整性及通信连通性的研究。

在《视频传感器网络中最差情况覆盖研究)》(“Optimal Worst-Case Coverage
of Directional Field-of-View Sensor Networks”发表于SECON’06)文章中,作者
提出一种最佳多项式时间算法,用于研究视频传感器网络中最差情况覆盖问题。

从申请人目前掌握的专利资料来看,尚未发现有涉及视频传感器网络覆盖
增强实现方法的相关研究材料。而且,上述工作都只考虑到了传感器节点方向
性的感知特性,而没有考虑传感器节点传感方向的可调整特性(如:云台摄像
头具有推拉摇移功能),而这个显著特点势必赋予视频传感器网络覆盖控制更为
丰富的含义,成为视频传感器网络系统的重要技术特征。

在视频传感器网络的初始部署阶段,为获得理想的传感器网络感知能力,
通常希望网络中视频传感器节点能最大限度地对目标区域实施覆盖。但是,视
频传感器网络往往工作在未知的、复杂的环境下,难以通过人为干预将众多视
频传感器节点放置在比较适宜的位置。在大规模随机部署模式下,必须部署远
大于实际需要的冗余视频传感器节点,才能满足预期的网络覆盖质量。此时,
很容易造成网络覆盖的不合理(如:局部目标区域视频传感器节点分布过于密
集或过于稀疏),形成感知重叠区和盲区。

在传统基于全向感知模型的传感器网络中,通常采用休眠冗余传感器节点、
重新调整传感器节点位置分布或添加新传感器节点等方法实现网络对目标区域
的覆盖。而在实际应用中,考虑到网络部署成本,所有部署的视频传感器节点
都具有移动能力是不现实的,而且视频传感器节点位置的移动只能发生在较近
范围内。

发明内容

有鉴于此,本发明的目的是提供一种成本有效的视频传感器网络覆盖增强
的实现方法,该方法能够解决两个问题:一是确定满足实际监测需求的视频传
感器网络中部署的视频传感器数目,以节约网络成本,即所谓成本有效;二是
通过调整视频传感器节点的传感方向,达到消除视频传感器网络中感知重叠区
和盲区的目的,进而提高视频传感器网络覆盖率和目标探测率。

为了达到上述目的,本发明提供了一种成本有效的视频传感器网络覆盖增
强的实现方法,其特征在于:包括下述两个操作步骤:

(1)部署阶段:根据实际监测需求,估算出所需部署的视频传感器节点数
目,并采用随机方式部署在目标区域内;该网络中所有视频传感器节点均同构,
且所有视频传感器节点一经部署位置固定不变,但都可调整各自的传感方向;

(2)调整阶段:在视频传感器节点位置固定的情况下,调整各个视频传感
器节点的传感方向,以消除视频传感器网络中感知重叠区和盲区,以较小的代
价增强视频传感器网络对目标区域的覆盖性能。

所述视频传感器网络由具有信息采集、转发和简单信号处理能力的多个视
频传感器节点和采用有线或无线方式与各视频传感器节点进行通信交互的汇聚
节点组成;其中视频传感器节点通过GPS定位设备获得自身位置信息,且可发
送控制指令来调整自身的传感方向,将该视频传感器节点采集的图像、视频数
据沿着其他视频感器节点逐跳传输,经过“多跳”路由传送到汇聚节点;汇聚
节点负责连接视频传感器网络与Internet或其它外部网络,发布并管理视频传
感器节点的监测任务。

所述视频传感器节点的感知范围是以传感器节点为圆心,与感知距离和感
知视角相关联的一个采用四元组<P,R, α>表示的扇形区域,其中,P=(x,y)
为视频传感器节点的位置坐标,R为传感器节点的最大传感范围-传感半径,
单位向量 V ( t ) = ( V X ( t ) , V Y ( t ) ) ]]>为感知区域的中轴线,即视频传感器节点在某一时刻
t时的传感方向, 分别是单位向量 在X轴和Y轴方向上的投影分量,
α为边界距离传感向量 的传感偏移角度,2α为感知视角。

所述步骤(1)进一步包括下列操作内容:

(11)确定监测需求:根据实际监测需求,得到下述监测参数:目标区域
面积S、单位为m2,视频传感器节点传感半径R、单位为m,感知视角2α、单
位为弧度,以及预期达到的网络覆盖率pexpected、单位为百分比;并假设目标区
域内任意两个视频传感器节点不在同一位置,且随机部署的视频传感器节点位
置均满足均匀分布;

(12)估算节点数目:根据随机部署策略和所述监测参数,建立统一的概
率模型,用于估算所需部署的视频传感器节点数目,以满足步骤(11)中预期
达到的网络覆盖率pexpected

(13)实施随机部署:根据步骤(12)中的计算结果,采用抛洒、喷射或
其它方式一次性随机地部署相应数目的视频传感器节点于目标区域中。

所述步骤(11)进一步包括下列操作:先将整个目标区域划分为若干等间
隔的网格,这些网格以及网格与目标区域的边界组成目标子区域;如果目标子
区域划分得足够小,则认为子区域中心点的覆盖率就是该子区域的覆盖率,且
视频传感器网络覆盖率p=‖ΛCovered‖/‖ΛTotal‖;式中,‖ΛCovered‖为被网络中视频传感
器节点覆盖的子区域数目,‖ΛTotal‖为目标区域中所有子区域中心点的数目,即
采用类似于模拟信号数字化的方法,将对目标区域的覆盖增强问题转化为对子
区域中心点的覆盖增强问题;

所述目标区域中子区域中心点被一个视频传感器节点覆盖的判定规则是:
先判定该子区域中心点与视频传感器节点间的距离是否不大于视频传感器节点
传感半径R?若不是,则该子区域中心点未被该视频传感器节点覆盖;若是,
则再根据该视频传感器节点的传感方向信息判定该子区域中心点是否在该视频
传感器节点的感知视角内?若不是,则该子区域中心点不被该视频传感器节点
覆盖;若是,该子区域中心点被该视频传感器节点覆盖;

所述一个子区域中心点被视频传感器网络覆盖的判定规则是:如果一个子
区域中心点被视频传感器网络中至少一个视频传感器节点覆盖,则认定该子区
域中心点被视频传感器网络覆盖。

所述建立统一的概率模型,用于估算所需部署的视频传感器节点数目的方
法为:在不考虑视频传感器节点可能落入边界区域造成有效覆盖面积的减小的
前提下,每个视频传感器节点所监测的区域面积为aR2,则每个视频传感器节点
所能监测整个目标区域S的概率为aR2/S,目标区域被数目为N的视频传感器
节点覆盖的概率p的计算公式为: p = 1 - ( 1 - aR 2 S ) N , ]]>N为自然数;则目标区域
内期望达到的网络覆盖率至少为pexpected时,需要部署的视频传感器节点数目
Nexpected的计算公式为: N expected ln ( 1 - p ) ln ( S - aR 2 ) - ln S . ]]>

所述步骤(2)进一步包括下列操作内容:

(21)划分传感连通子图:先将视频传感器网络抽象为无向图G(V(G),
E(G)),其中V(G)为无向图G的节点集,即视频传感器节点集;E(G)为
无向图G的边集;再以“邻接点”为依据划分传感连通子图,所谓邻接点是两
个节点vi和vj之间的距离不大于其传感半径的两倍时,即节点vi和vj之间的距
离长度eij≤2R,则节点vi和vj互为邻接点,记作eij∈E(G);

(22)生成多层凸包集:在各传感连通子图中同时进行该操作,为每个传
感连通子图由外层到内层建立多层凸包集,以便将各传感连通子图覆盖增强问
题分而治之地转化为两个凸包夹层地带的覆盖增强问题;

(23)计算各传感器节点的新传感方向并进行调整:由于此时网络中每个
视频传感器节点仅属于某一层凸包,则将该凸包上的某个节点vij分别连接与其
同层左右两侧的两个邻居节点vi-1j、vi+1j,得到相应的两个边e(i-1)(i)j、e(i)(i+1)j;再
对节点vij计算该两个边e(i-1)(i)j、e(i)(i+1)j所构成的夹角2βij∈[0,π],以及对节点vij
算夹角2βij的平分线,用于自动调整该节点vij的传感方向:使该节点vij的新传
感方向与夹角2βij的外角平分线同向,实现视频传感器网络覆盖增强。

所谓节点集V(G)的凸包是指每个传感连通子图中的一个最小凸多边形,
满足节点集V(G)中的点位于该多边形的边上或该多边形内部,则由处于最外
围的点所连接组成的多边形即为节点集V(G)的凸包。

所述步骤(22)生成多层凸包集的具体操作步骤为:

(221)选取当前传感连通子图中纵坐标值最小的点v1,如果纵坐标最小值
的节点有多个时,则选取最左边的节点;

(222)对当前传感连通子图中剩余的各个节点分别按逆时针方向、相对节
点v1的极角进行排序;若这样的节点有多个,则仅取其中一个与该节点v1距离
最远的节点,其他节点都被滤除掉;再假设已经选好下述各个节点:v1,v2,v3,...,
vN

(223)设定一个堆栈,先将前三个节点v1,v2,v3依次入栈,其它的节点
随后逐个入栈,且仅入栈一次,按照不是凸包边上的节点将从栈顶弹出的方法
来确定凸包的点,即栈里的节点即为凸包的点;

(224)循环执行上述步骤(221)~(223)的操作,直到当前传感连通子
图中的所有节点都属于某层凸包。

所述步骤(223)中,检验栈顶元素是否为凸包上的点的规则是:

(a)判断栈顶元素vtop和次栈顶元素vtop-1以及所考察的节点vi(i∈[4,N])
所形成角是否呈逆时针旋转?若是,栈顶元素不出栈;否则,栈顶元素出栈;

(b)将i赋值为节点序列中节点vi下一个节点的标号,并将节点vi进栈,
继续考察栈顶元素vtop、次栈顶元素vtop-1和所考察的节点vi,循环步骤(a)的
操作。

本发明是一种成本有效的视频传感器网络覆盖增强的实现方法,它是从视
频传感器节点方向性感知特点出发,基于视频传感器节点初始位置固定不变的
假设,通过调整视频传感器节点的传感方向来增强视频传感器网络覆盖。下面
分别从节约网络部署成本和增强网络覆盖性能两方面说明本发明方法的优点:

从节约网络部署成本的角度上来看,本发明提出利用统一的概率模型来估
算满足期望网络覆盖率pexpected时所需部署的视频传感器节点数目Nexpected,以便
有效控制视频传感器网络中节点分布密度,进而节约网络部署成本。

从增强网络覆盖性能的角度上来看,本发明充分考虑到视频传感器节点方
向性的感知特性,提出一种不同于传统的利用传感器节点位置移动增强视频传
感器网络覆盖的新思路:通过视频传感器节点传感方向的自调整,达到消除视
频传感器网络中感知重叠区和盲区的目的,以较小的代价增强视频传感器网络
对目标区域的覆盖,明显改善视频传感器网络对监控区域的目标探测能力。

从增强网络覆盖性能的实现方法上来看,本发明基于图论方法将视频传感
器网络抽象为无向图。通过定义“邻接点”的概念将整个视频传感器网络划分
为若干个传感连通子图。属于不同传感连通子图的一对视频传感器节点,其传
感方向的调整不受对方影响(即当一对视频传感器节点之间距离大于或等于节
点传感半径的两倍时,无论其传感方向取值如何,都不可能形成感知重叠区域)。
通过划分传感连通子图的方法,将整个视频传感器网络覆盖增强问题分而治之
地转化为各传感连通子图覆盖增强问题。接着,为各传感连通子图由外(层)
到内(层)建立多层凸包集,将各传感连通子图覆盖增强问题转化为两凸包夹
层地带的覆盖增强问题。经过上述两次问题转化,大大地降低了发明方法的计
算复杂度,加速了网络覆盖增强进程。

总之,本发明一种成本有效的视频传感器网络覆盖增强的实现方法具有很
好的应用前景。

附图说明

图1是本发明视频传感器网络覆盖增强的实现方法的操作步骤方框图。

图2是视频传感器网络结构组成示意图。

图3是视频传感器网络覆盖率的计算示意图。

图4(A)、(B)分别是全向感知模型和有向感知模型的两种传感器节点感
知模型示意图。

图5是视频传感器节点的方向可调感知模型示意图。

图6(A)、(B)分别是两节点互为邻接点和两节点不互为邻接点的示意图。

图7(A)、(B)分别是划分传感连通子图的操作步骤示意图。

图8是节点集凸包示意图。

图9是本发明采用的生成多层凸包集的示意图。

图10是本发明采用的生成多层凸包集的节点出入栈示意图。

图11是本发明计算各传感器节点的新传感方向并进行调整的示意图。

图12(A)、(B)分别是计算各视频传感器节点的理想传感方向并进行调
整的视频传感器网络实施例的调整前、后网络布局示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚,下面结合附图对本发明作
进一步的详细描述。

参见图1,本发明是一种成本有效的视频传感器网络覆盖增强的实现方法,
包括下述两个操作步骤:

(1)部署阶段:根据实际监测需求,估算出所需部署的视频传感器节点数
目,并采用随机方式部署在目标区域内;该网络中所有视频传感器节点均同构,
且所有视频传感器节点一经部署位置固定不变,但都可调整各自的传感方向;

(2)调整阶段:在视频传感器节点位置固定的情况下,调整各个视频传感
器节点的传感方向,以消除视频传感器网络中感知重叠区和盲区,以较小的代
价增强视频传感器网络对目标区域的覆盖性能。

参见图2,先简要介绍视频传感器网络:由具有信息采集、转发和简单信
号处理能力的多个视频传感器节点和采用有线或无线方式与各视频传感器节点
进行通信交互的汇聚节点组成;其中视频传感器节点通过GPS定位设备获得自
身位置信息,且可通过发送控制指令方式调整自身的传感方向。视频传感器节
点采集的图像、视频数据沿着其他视频感器节点逐跳进行传输,经过“多跳”
路由传送到汇聚节点。汇聚节点负责连接视频传感器网络与Internet等外部网
络,发布管理传感器节点的监测任务。

参见图3,为简化问题,本发明将整个目标区域划分为若干等间隔的网格,
这些网格以及网格与目标区域的边界组成了目标子区域。如果子区域划分的足
够小,子区域中心点的覆盖率就可认为是该子区域的覆盖率,所有子区域中心
点所构成的集合用ΛTotal表示。以此方法,本发明将对目标区域的覆盖增强问题
转化为对子区域中心点的覆盖增强问题。假设被视频传感器节点覆盖的子区域
中心点集合为ΛCovered,则视频传感器网络覆盖率p=‖ΛCovered‖/‖ΛTotal‖,其中
‖ΛCovered‖表示被网络中视频传感器节点覆盖的子区域数目,‖ΛTotal‖表示目标区域
中所有子区域中心点的数目。这种问题映射方法类似于模拟信号数字化,既可
有效地描述问题,也可大大地简化计算复杂度。

图3中,将目标区域划分为10×10个子区域(用小方格表示),两个视频
传感器节点(用空心圆点表示)所能覆盖到的子区域中心点数目(用实心圆点
表示)为21个。因此,当前视频传感器网络覆盖率p=21/100=21%。

下面针对上述两个阶段,详细介绍本发明实现方法的具体操作步骤。

视频传感器网络的初期部署有两种策略:一种是大规模的随机分散
(Scattering模式);另一种是针对特定用途进行有目的设置(Planning模式)。
在第一种随机分布模式下,为取得较好的视频传感器网络覆盖性能,必须投入
远大于实际需要的冗余视频传感器节点。若要达到较为理想的传感器网络覆盖
性能,网络中视频传感器节点的分布密度要相当高。因此,本发明设计一种估
算满足实际监测需求的视频传感器节点部署数目的方法,以节约网络成本。

参见图4,有别于传统基于全向感知模型的传感器节点(其感知范围是一
个以传感器节点为圆心,感知距离为半径的圆形区域,如图4(A)所示),视
频传感器节点的感知能力受到方向性限制,即其感知范围是一个以传感器节点
为圆心,与感知距离和感知视角相关的扇形区域,如图4(B)所示。

参见图5,介绍本发明对传统有向感知模型进行改进的方法:考虑到视频
传感器节点具有传感方向可调整特性,设计了新型的方向可调感知模型:用一
个四元组<P,R, α>来表示,其中用空心圆点表示的P=(x,y)为视频传感器节
点的位置坐标;R为传感器节点的最大传感范围,即传感半径;单位向量 V ( t ) = ( V X ( t ) , V Y ( t ) ) ]]>
为感知区域的中轴线,即视频传感器节点在某一时刻t时的传感方
向; 分别是单位向量 在X轴和Y轴方向上的投影分量;α为边界距
离传感向量 的传感偏移角度,2α代表感知视角。当α=π时,传统的全向感
知模型是有向感知模型的一个特例。

图5中的目标区域中子区域中心点(用实心圆点表示)被一个视频传感器
节点覆盖的判定规则是:先判定该子区域中心点与视频传感器节点之间的距离
是否小于等于视频传感器节点传感半径R?若不是,则该子区域中心点不被该
视频传感器节点覆盖;若是,则需要再根据该视频传感器节点的传感方向信息
判定该子区域中心点是否在该视频传感器节点的感知视角内?若不是,则该子
区域中心点不被该视频传感器节点覆盖;否则,该子区域中心点被该视频传感
器节点覆盖。一个子区域中心点被视频传感器网络覆盖的判定规则是:如果一
个子区域中心点被视频传感器网络中至少一个视频传感器节点覆盖,那么我们
认定该子区域中心点被视频传感器网络覆盖。

本发明方法的(1)部署阶段又可细分为以下三个子阶段:

(11)确定监测需求:根据实际监测需求,得到以下监测参数:目标区域
面积S(单位:m2)、视频传感器节点传感半径R(单位:m)和感知视角2α(单
位:弧度),以及预期达到的网络覆盖率pexpected(单位:百分比)。假设目标区
域内任意两个视频传感器节点不在同一位置,且随机部署的视频传感器节点位
置均满足均匀分布。

(12)估算节点数目:根据随机部署策略以及子阶段(11)中监测参数,
建立统一的概率模型,用于估算所需部署的视频传感器节点数目,以满足子阶
段(11)中预期达到的网络覆盖率pexpected。其中建立统一的概率模型以估算所
需部署的视频传感器节点数目的具体方法为:不考虑视频传感器节点可能落入
边界区域造成有效覆盖面积的减小的前提下,由于每个视频传感器节点所监测
区域的面积为aR2,则每个视频传感器节点所能监测整个目标区域的概率为
aR2/S。因此,目标区域被N个视频传感器节点覆盖的概率的计算公式为:

p = 1 - ( 1 - aR 2 S ) N , ]]>

由此,目标区域内期望达到的网络覆盖率至少为pexpected时,需要部署的视
频传感器节点数目Nexpected的计算公式为: N expected ln ( 1 - p ) ln ( S - aR 2 ) - ln S ; ]]>

(13)实施随机部署:根据子阶段(12)的计算结果,采用抛洒、喷射等
方式一次性随机地部署相应数目的视频传感器节点于目标区域中。

当视频传感器节点部署在目标区域中后,本发明要对视频传感器节点的传
感方向进行调整,以增强视频传感器网络覆盖性能。该(2)调整阶段又分为以
下三个子阶段:

(21)划分传感连通子图:先将视频传感器网络抽象为无向图G(V(G),
E(G)),其中V(G)为无向图G的节点集(视频传感器节点集);E(G)为
无向图G的边集。eij表示节点vi和vj之间的边。

参见图6,介绍“邻接点”的概念:当节点vi和vj间距离小于等于其传感
半径的两倍时(即eij≤2R),认定节点vi和vj互为邻接点,记作eij∈E(G)。如
图6(A)所示,节点vi和vj互为邻接点,说明(视频传感器)节点vi和vj
过传感方向的调整有可能形成覆盖重叠区域;反之,无论节点vi和vj的传感方
向无论取何种方向,都不可能形成覆盖重叠区域,如图6(B)所示。也就是说,
只有当节点vi和vj互为邻接点时,传感方向的调整才受到对方影响;否则,传
感方向的调整相互独立。

无向图G中节点具有访问状态属性,取值为“Y”或者“N”,分别表示已
访问和未访问。起初,所有节点的访问状态取值均为“N”。当节点归属于某个
传感连通子图时,其访问状态取值也随即修改为“Y”。本发明通过修改节点的
访问状态取值,以区分当前节点是否已归属于某个传感连通子图。

参见图7。介绍传感连通子图SCSG(Sensing Connected Sub-Graph)的生
成方法的具体操作步骤,其中NSCSG表示无向图G中包含的传感连通子图数目。

步骤1:从无向图G中一个节点v出发,将所有与节点v互为邻接点、且
访问状态取值为“N”的节点加入到传感连通子图SCSGi(i∈NSCSG)节点集中,
修改节点v的访问状态取值为“Y”;

步骤2:分别从这些新加入的节点出发,重复步骤1操作,直到再没有满
足条件的节点可加入到SCSGi节点集中,且SCSGi节点集中所有节点的访问状
态取值为“Y”。

步骤3:从无向图G中任意一个访问状态取值为“N”的节点出发,重复
步骤1和步骤2操作,直到无向图G中所有节点都被划分到某个传感连通子图
SCSGi

对图7(A)所示网络实例进行传感连通子图划分,得到图7(B)中的7
个传感连通子图,分别以相应数字标号进行标识。在图7(B)中,如果两节点
互为邻接点,则用直线连接。

下面以SCSG5为例,具体说明传感连通子图的生成过程:在生成SCSG4
以后,无向图G中尚存在访问状态取值为“N”的节点。假设随机选定从节点
1出发,此时,SCSG5={节点1(N)}。

将所有与节点1互为邻接点、且访问状态取值为“N”的节点加入到传感
连通子图SCSG5节点集中,并修改节点1的访问状态取值为“Y”。此时,
SCSG5={节点1(Y),节点2(N),节点3(N),节点4(N),节点5(N),
节点6(N),节点7(N),节点8(N)}。

分别从这些新加入的节点(即访问状态取值为“N”的节点)出发,将所
有与新加入节点互为邻接点、且访问状态取值为“N”的节点加入到传感连通
子图SCSG5节点集中,并修改节点1~节点8的访问状态取值为“Y”。此时,
SCSG5={节点1(Y),节点2(Y),节点3(Y),节点4(Y),节点5(Y),
节点6(Y),节点7(Y),节点8(Y),节点9(N),节点10(N),节点11
(N),节点12(N),节点19(N)}。

分别从这些新加入的节点(即访问状态取值为“N”的节点)出发,将所
有与新加入节点互为邻接点、且访问状态取值为“N”的节点加入到传感连通
子图SCSG5节点集中,并修改节点9、节点10、节点11、节点12、节点19的
访问状态取值为“Y”。此时,SCSG5={节点1(Y),节点2(Y),节点3(Y),
节点4(Y),节点5(Y),节点6(Y),节点7(Y),节点8(Y),节点9(Y),
节点10(Y),节点11(Y),节点12(Y),节点19(Y),节点13(N),节点
14(N),节点15(N),节点20(N)}。

分别从这些新加入的节点(即访问状态取值为“N”的节点)出发,将所
有与新加入节点互为邻接点、且访问状态取值为“N”的节点加入到传感连通
子图SCSG5节点集中,并修改节点13、节点14、节点15、节点20的访问状态
取值为“Y”。此时,SCSG5={节点1(Y),节点2(Y),节点3(Y),节点4
(Y),节点5(Y),节点6(Y),节点7(Y),节点8(Y),节点9(Y),节
点10(Y),节点11(Y),节点12(Y),节点19(Y),节点13(Y),节点14
(Y),节点15(Y),节点20(Y),节点16(N),节点17(N),节点18(N),
节点21(N)}。

分别从这些新加入的节点(即访问状态取值为“N”的节点)出发,将所
有与新加入节点互为邻接点且访问状态取值为“N”的节点加入到传感连通子
图SCSG5节点集中,并修改节点16、节点17、节点18、节点21的访问状态取
值为“Y”。此时,SCSG5={节点1(Y),节点2(Y),节点3(Y),节点4(Y),
节点5(Y),节点6(Y),节点7(Y),节点8(Y),节点9(Y),节点10(Y),
节点11(Y),节点12(Y),节点19(Y),节点13(Y),节点14(Y),节点
15(Y),节点20(Y),节点16(Y),节点17(Y),节点18(Y),节点21
(Y),节点22(N)}。

SCSG5中仅有一个新加入的节点(节点22),从节点22出发,将所有与节
点22互为邻接点、且访问状态取值为“N”的节点加入到传感连通子图SCSG5
节点集中,并修改节点22的访问状态取值为“Y”。此时,SCSG5={节点1(Y),
节点2(Y),节点3(Y),节点4(Y),节点5(Y),节点6(Y),节点7(Y),
节点8(Y),节点9(Y),节点10(Y),节点11(Y),节点12(Y),节点19
(Y),节点13(Y),节点14(Y),节点15(Y),节点20(Y),节点16(Y),
节点17(Y),节点18(Y),节点21(Y),节点22(Y),节点23(N)}。

从SCSG5中仅有一个访问状态取值为“N”的节点23出发,再没有满足条
件的节点可加入到SCSG5节点集中,则修改节点23的访问状态取值为“Y”。
节点集SCSG5生成完毕。

一个视频传感器网络所包含的传感连通子图数目NSCSG在一定程度上说明
了网络中视频传感器节点的分布密度。由于采用随机部署策略,视频传感器网
络所包含的传感连通子图数目NSCSG越多,说明该视频传感器网络中存在的网
络覆盖盲区越多;因此,利用本发明方法对视频传感器网络覆盖增强也就越显
著。这样,本发明就利用传感连通子图的概念,将整个视频传感器网络覆盖增
强问题分而治之,进而转化为各传感连通子图覆盖增强问题。

(22)生成多层凸包集:该操作在各传感连通子图中同时进行,为每一个
传感连通子图由外(层)到内(层)建立多层凸包集,进而将各传感连通子图
覆盖增强问题分而治之,转化为两凸包夹层地带覆盖增强问题。

参见图8,介绍凸包的概念:节点集V(G)的凸包是指一个最小凸多边形,
满足节点集V(G)中的点或者在多边形边上或者在其内。由粗线段表示的多边
形就是节点集V(G)的凸包。

为各传感连通子图由外(层)到内(层)建立多层凸包集的目的有二:a)
凸包是存在最为广泛的一种计算几何图形。对于任意位于同一个二维平面中的
离散点集,总能找到相应的凸包。b)多层凸包集可以有效地将一个传感连通子
图覆盖的区域划分为若干个包夹层覆盖的区域,使得问题进一步简化。

在此,描述生成多层凸包集的具体步骤:

a)选取当前传感连通子图中纵坐标值最小的点v1,如果具有纵坐标最小值
的节点有多个,则取最左边的那个节点。

b)对当前传感连通子图中剩余节点按逆时针相对节点v1的极角进行排序。
若有多个这样的节点,则仅取一个与节点v1距离最远的节点,其他的节点被滤
除掉,假设v1,v2,v3,…,vN已经选好。

c)设定一个堆栈,先将v1,v2,v3依次入栈,其它的节点随后逐个入栈且
仅入栈一次,不是凸包上的节点将从栈顶弹出,以此方法确定凸包的点。检验
栈项元素是否为凸包的点的规则是:先判断栈顶元素vtop和次栈顶元素vtop-1
所考察的节点vi(i∈[4,N])所形成角是否呈逆时针旋转?若是,栈顶元素不出
栈;否则,栈顶元素出栈。然后将i赋值为节点序列中节点vi下一个节点的标
号,并将节点vi进栈,继续考察栈顶元素vtop、次栈顶元素vtop-1和所考察的节
点vi,循环前面步骤的操作。

d)栈里的节点即为凸包的点。

e)循环上述步骤a)~d)操作,直到当前传感连通子图中所有节点都属
于某层凸包。

参见图9。介绍本发明采用上述方法由外(层)到内(层)逐步建立多层
凸包集合的操作:先选取当前传感连通子图((A)图)中纵坐标值最小的节点
v1。其次,当前传感连通子图中剩余的节点按逆时针相对节点v1的极角进行排
序。节点序列为:v1,v2,v3,v5,v6,v7,v8。对于节点v3和v4,由于它们相对
于节点v1的极角相等(即v1,v3,v4共线),则按照如下原则进行取舍:选取两
者中距离节点v1最远的节点v3,而将节点v4滤除掉。然后设定一个堆栈,先将
v1,v2,v3依次入栈(参见图10(a)),其它的节点随后逐个入栈,且仅入栈一
次,不是凸包上的节点将从栈顶弹出,以此方法确定凸包的点。最后,栈里的
节点即为凸包的点。

检验栈顶元素是否为凸包的点的具体步骤为:

(1)取节点序列中第4个节点v5,判断栈顶元素v3和次栈顶元素v2及所
考察的节点v5所形成角是否呈逆时针旋转。如图9中加粗折线所示,节点v3
v2及v5所形成角呈逆时针旋转,所以栈顶元素v3不出栈。节点v5进栈,如图
10(b)所示。

(2)取节点序列中第5个节点v6,判断栈顶元素v5和次栈顶元素v3及所
考察的节点v6所形成角是否呈逆时针旋转。节点v5、v3及v6所形成角不呈逆时
针旋转,所以栈顶元素v5出栈。节点v6进栈,如图10(c)所示。

(3)取节点序列中第6个节点v7,判断栈顶元素v6和次栈顶元素v3及所
考察的节点v7所形成角是否呈逆时针旋转。节点v6、v3及v7所形成角呈逆时针
旋转,所以栈顶元素v6不出栈。节点v7进栈,如图10(d)所示。

(4)取节点序列中第7个节点v8,判断栈顶元素v7和次栈顶元素v6及所
考察的节点v8所形成角是否呈逆时针旋转。节点v7、v6及v8所形成角不呈逆时
针旋转,所以栈顶元素v7出栈。节点v8进栈,如图10(e)所示。

经过上述操作,栈里的节点v1,v2,v3,v6,v8即为最外层凸包的点。

对于剩余的节点v4,v5,v7,则循环进行上述操作:先选取当前传感连通子
图中剩余的纵坐标值最小的节点v7。再将当前传感连通子图中剩余的节点按逆
时针相对节点v7的极角进行排序。节点序列为:v7,v4,v5。显然,这三个点可
直接构成第二层凸包。由此,当前传感连通子图中所有节点都属于某层凸包,
多层凸包集生成完毕。

经历子阶段(21)和(22)后,无向图G节点集V(G)中的每个节点vi
(i∈Nexpected)都位于某个传感连通子图的某层凸包上。本发明用vij表示第j层
闭包上的第i个节点,vi-1j和vi+1j分别为第j层闭包上的第i个节点的左右相邻节
点,e(i)(i+1)j表示第j层闭包上的第i个节点与同层闭包上的第i+1个节点间的边。

(23)计算各传感器节点的新传感方向并调整:此时,网络中每个视频传
感器节点仅属于某一层凸包(如图11所示),再让vij分别与其同层左右两个邻
居节点vi-1j、vi+1j相连,得到相应的边e(i-1)(i)j、e(i)(i+1)j。节点vij计算两个边e(i-1)(i)j
e(i)(i+1)j所构成的夹角(2βij∈[0,π]);节点vij计算夹角平分线,并自动调整其传
感方向,使之与夹角的外角平分线同向,最终实现视频传感器网络覆盖增强。

最后,具体介绍申请人进行试验实施的一个成本有效的视频传感器网络覆
盖增强实施例。

在500×500m2的目标区域内,部署传感半径R=50m、传感偏移角度α=π/3
的视频传感器节点完成场景的监测。若预期达到的网络覆盖率pexpected=80%,
通过前述公式可估算出所需部署的视频传感器节点数目:

N = ln ( 1 - 0.80 ) ln ( 250000 - 0.33 π × 50 × 50 ) - ln ( 250000 ) = 152 . ]]>

我们在目标区域中随机部署了152个视频传感器节点。如图12(A)所示,
网络中所有视频传感器节点的位置和传感方向信息都是随机生成的,不可避免
地会导致网络中视频传感器节点覆盖能力不均匀,初始网络覆盖率为80.37%。
分布过于密集的多个相邻视频传感器节点间形成感知重叠区会大大浪费视频传
感器网络资源;而视频传感器节点分布过于稀疏的区域是视频传感器网络无法
监测到的区域,一旦这些盲区出现目标,视频传感器网络将无能为力。

利用本发明方法,视频传感器网络中位置固定但传感方向可调整的众多视
频传感器节点进行传感方向的重新调整。其结果如图12(B)所示,经过多次
调整,多个相邻视频传感器节点间的冗余覆盖显著降低,有效地增强了整个视
频传感器网络的覆盖性能,网络覆盖率增强至87.03%。

该实施例通过视频传感器节点传感方向的自调整,在仅仅部署152个视频
传...

=>>详细说明书全文请进入首页检索查看

图1
©2018 IPPH.cn   PatViewer·专利搜索
主办单位:知识产权出版社有限责任公司  咨询热线:01082000860-8588
浏览器:IE9及以上、火狐等  京ICP备09007110号 京公网安备 11010802026659号