PatViewer专利搜索

一种非规则区域的无线传感器网络节点部署方法

发明公布  有效
申请(专利)号:CN201610513303.2国省代码:广东 44
申请(专利权)人:广东工业大学
温馨提示:Ctrl+D 请注意收藏,详细著录项请首页检索查看。 Please note the collection. For details, please search the home page.

摘要:
本发明公开了一种非规则区域的无线传感器网络节点部署方法,用以解决边界非规则的监测区域难以确定节点部署位置及节点数量代价高的问题。该方法包括:步骤1,生成非规则监测区域的外廓四边形;步骤2,根据节点的感知半径r,生成边长为r的正六方形,并以此正六方形构造蜂窝结构;步骤3,利用步骤2生成的蜂窝结构对步骤1的外廓四边形进行确定性最优部署;步骤4,剔除冗余的传感器节点,即把感知范围在待监测区域以外的节点剔除掉,剩下的节点即为实现该非规则区域全覆盖所需的最少节点。本发明能够确定非规则区域的无线传感器节点的部署位置,并以最少的节点数对其实现全覆盖。

主权项:
一种非规则区域的无线传感器网络节点部署方法,其特征在于,包括以下步骤:步骤1,生成非规则监测区域的外廓四边形:提取该区域的边界,根据边界上的点生成所述外廓四边形;步骤2,构造蜂窝结构:假设节点感知半径为r,以r为边长生成正六方形,并以此正六方形构造蜂窝结构;步骤3,外廓四边形节点部署:利用步骤2中生成的蜂窝结构对步骤1中生成的外廓四边形进行确定性的优化部署,使部署的节点最少;步骤4,剔除冗余节点:遍历所有节点,把节点感知范围与待监测区域没有交集的节点剔除掉,剩下的节点即为对该非规则区域进行的最优部署节点。


说明书

一种非规则区域的无线传感器网络节点部署方法

技术领域

本发明涉及无线传感器网络领域,特别的涉及一种非规则区域的无线传感器网络
节点部署方法。

背景技术

无线传感器网络大大提高了人们获取信息的能力,在智能工厂、智能家居、环境监
测、智能农业等领域得到广泛的应用。对于智能工厂、智能家居、医院等室内环境或存在边
界的环境的无线传感器网络应用,其共同特点是监测区域都存在边界,所以,研究利用最少
的节点对边界区域进行确定性部署具有重要的实际意义,特别地,对于非规则区域的节点
部署更是一个难题。

对于边界区域的部署问题,目前研究成果还比较少,在文献《圆周对矩形区域的覆
盖》(“Covering a Rectangle With Equal Circles”,发表于期刊Periodica Mathematica
Hungarica,1997,34(1-2):65-81)中,A.Heppes求解出5个圆周和7个圆周所能覆盖的最大
矩形区域;文献《6和8圆周在正方形的优化覆盖》(“Improved coverings of a square
with six and eight equal circles”,发表于Electronic Journal of Combinatorics,3
(1),1996)中,Melissen解决了6个和8个圆周覆盖区域最大化的部署问题;文献《30个相同
圆周的正方形覆盖》(“Covering a square with up to 30equal circles”,发表于
Sabbagh,2000)中,Hgskolan T等人对正方形的圆周覆盖问题进行推广,求解出30个圆周的
覆盖区域最大化的部署问题。在文献《边界区域的无线网络覆盖》(“On Wireless Network
Coverage in Bounded Areas”,发表于国际会议INFOCOM 2013)中,Zuoming Yu等人提出了
利用蜂窝结构对矩形区域及基于矩形区域的一般区域的部署方法。

由以上可知,对于边界区域部署的研究成果还相当有限。大部分文献都是研究矩
形区域的覆盖问题,且目前的研究成果仅限于30个等圆周;文献《边界区域的无线网络覆
盖》取得一定突破,但也只是研究基于矩形的一般区域,对非规则区域则没有给出具体的方
法。

发明内容

本发明的目的在于,提供一种非规则区域的无线传感器网络节点部署方法,用以
解决边界非规则的监测区域难以确定节点部署位置及节点数量代价高的问题。

为实现以上目的,本发明提供的技术方案是,一种非规则区域的无线传感器网络
节点部署方法,其特征在于,包括以下步骤:

步骤1,生成非规则监测区域的外廓四边形:提取该区域的边界,根据边界上的点
生成其外廓四边形;

步骤2,构造蜂窝结构:假设节点感知半径为r,以r为边长生成正六方形,并以此正
六方形构造蜂窝结构;

步骤3,外廓四边形节点部署:利用步骤2中生成的蜂窝结构对步骤1中生成的外廓
四边形进行确定性的优化部署,使部署的节点最少;

步骤4,剔除冗余节点:遍历所有节点,把节点感知范围与待监测区域没有交集的
节点剔除掉,剩下的节点即为对该非规则区域进行的最优部署节点。

进一步的,所述步骤1包括:

步骤1.1,任取不包含边界的监测区域内的一点,作为直角坐标系的原点,遍历边
界上的点,分别标记横坐标值、纵坐标值最大及最小的点;

步骤1.2,对于具有横坐标值最大及最小的点,求出与这些点相交的与纵坐标轴平
行的两条直线;

步骤1.3,对于具有纵坐标值最大及最小的点,求出与这些点相交的与横坐标轴平
行的两条直线;

步骤1.4,那么,这4条线相交所形成的四边形即为该非规则区域的外廓四边形。

进一步的,所述步骤3包括:

利用蜂窝结构对外廓四边形进行确定性的优化部署指靠近边界处的蜂窝中的正
六边形与边界的对齐方式:

步骤3.1,对于外廓四边形平行于纵坐标轴的两条边,任选其中一条边V0,令靠近
V0的1列正六边形的中心点与V0的距离为d0=r*1/2;

步骤3.2,对于外廓四边形平行于横坐标轴的两条边,任选其中一条边H0,把靠近
H0的一排正六方形的中心点连成一条线,或平行于横坐标轴的边连成一条线L,令L与H0重
叠,该方式即是利用蜂窝结构在矩形边界区域的最优部署模式。

进一步的,所述步骤4具体是:在步骤3中蜂窝结构的每个正六边形的中心都部署
节点,节点的感知范围为半径等于r的圆形,遍历监测区域外的所有节点N,剔除掉感知范围
与监测区域不重叠的节点,那么,剩下的节点就是对该非规则区域的所部署的节点。

本发明解决了在无线传感器网络中能够非规则区域难以确定节点部署位置及节
点数量代价高的问题,对各种非规则区域具有较好的适应性,实现简单。

附图说明

图1为本发明提供的非规则区域的无线传感器网络节点部署方法流程图;

图2为边界非规则的监测区域;

图3为非规则区域中具有最大及最小横坐标值、纵坐标值的点;

图4为非规则区域的外廓四边形;

图5为边长为r的正六方形;

图6为边长为r的正六方形生成的蜂窝结构;

图7为利用蜂窝结构对外廓四边形进行优化部署;

图8为剔除掉冗余节点后的非规则区域的节点部署图;

具体实施方式

下面结合附图,对优选实施例作详细说明。应该说明的是,下述说明仅仅是示例性
的,而不是为了限制本发明的范围及其应用。

本发明提供一种非规则区域的无线传感器网络节点部署方法,其是一种基于蜂窝
结构的面向非规则区域的确定性部署方法。图1是本发明提供的非规则区域的无线传感器
网络节点部署方法流程图,其包括以下步骤:

步骤1:生成非规则监测区域的外廓四边形:提取该区域的边界,根据边界上的点
生成其外廓四边形。

图2为一边界非规则的监测区域,该监测区域可以为任意的凸或非凸形状的区域,
生成该区域外廓四边形的具体步骤是:

步骤1.1:如图3所示,任取该不规则监测区域内的一点OP(不包含边界)作为直角
坐标系的原点,并标出该直角坐标系,如图3中所示的直角坐标系;遍历边界上的点,分别标
记横坐标值、纵坐标值最大及最小的点,如图3所示,X1表示横坐标值最小的点,X2为横坐标
值最大的点,Y1为纵坐标值最小的点,Y2为纵坐标值最大的点;

步骤1.2:如图4所示,通过点X1作一直线LX1,并使该直线与纵坐标轴平行;同理,通
过点X2作一直线LX2,并使该直线与纵坐标轴平行。

步骤1.3:如图4所示,通过点Y1作一直线LY1,并使该直线与横坐标轴平行;同理,通
过点Y2作一直线LY2,并使该直线与横坐标轴平行。

步骤1.4:如图4所示,直线LX1、LX2、LY1、LY2相交于4个点A、B、C、D,线段AB、BC、CD、DA
所形成的四边形即为该非规则区域的外廓四边形S。

步骤2,构造蜂窝结构:假设节点感知半径为r,以r为边长生成正六方形,并以此正
六方形构造蜂窝结构。

如图5所示,传感器节点N1的感知范围是半径为r的圆,感知范围内所发生的事件
均能被该节点所检测到。在文献《区域覆盖的圆周数量》(“The number of circles
covering a set”,发表于American Journal of Mathematics,61:665-671,1939)中,克什
纳证明了蜂窝结构是无边界区域的最优覆盖模式,即对同等面积区域进行全覆盖时,蜂窝
结构所需节点数量最少。因此,本发明以r为边长构造图5中的正六变形O,并以S为单元构造
图6的蜂窝H。

步骤3:外廓四边形节点部署:利用步骤2中生成的蜂窝结构对步骤1中生成的外廓
四边形进行确定性的优化部署,使部署的节点最少。

图7中,利用蜂窝结构H对外廓四边形S进行确定性的优化部署时,当蜂窝单元所在
位置远离边界时,其部署如同无边界区域;当靠近边界时,需对蜂窝单元的位置作精确部
署,具体过程如下:

步骤3.1:对于外廓4边形S平行于纵坐标轴的两条边V0及V1,任选其中一条边V0,
令靠近V0的蜂窝H中1列正六边形的中心点,如图7中的中心点CP与V0的距离为d0=r*1/2,
这样部署的优点是实现了边界区域的全覆盖,同时没有浪费节点的覆盖能力;

步骤3.2:对于外廓4边形S平行于横坐标轴的两条边H0及H1,任选其中一条边H0,
把靠近H0的一排正六方形的中心点连成一条线,或平行于横坐标轴的边连成一条线L,令L
与H0重叠,该方式即是利用蜂窝结构在矩形边界区域的最优部署模式。

必须强调的是,当V1、H1边界处的蜂窝对齐方式分别跟V0、H0一致时,此时达到了
最优的部署;但由于外廓四边形的边长跟节点的感知半径是常量,很难同时保证4个边界同
时达到最优化部署,但至少可保证相邻两条边实现最优化部署,所以,对外廓四边形进行部
署时一般选相邻的两条边进行如图7所示的最优化部署。

步骤4:剔除冗余节点:遍历所有节点,把节点感知范围与待监测区域没有交集的
节点剔除掉,剩下的节点即为对该不规则区域进行的最优部署节点。

具体过程是:在图7中的蜂窝结构的每个正六边形的中心都部署节点,节点的感知
范围为半径等于r的圆形,遍历监测区域外的所有节点N,剔除掉感知范围与监测区域不重
叠的节点,那么,剩下的节点就是对该不规则区域的所部署的节点,如图8所示。可以证明,
对外廓四边形的蜂窝结构部署是节点数量最小化的最优部署,而步骤4剔除了最大数量的
冗余节点,所以本发明实现了对非规则区域的节点数量最小化的最优化部署。

...

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

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