面向双层结构无线传感器网络的中继节点鲁棒覆盖方法

1.一种面向双层结构无线传感器网络的中继节点鲁棒覆盖方法，其特征在于，包括以下步骤：
首次1-覆盖：包括中继节点候选位置构建阶段、传感器节点分组阶段和局部部署阶段；
所述中继节点候选位置构建阶段根据所需覆盖的传感器节点方位信息，构建全部中继节点的候选部署方位；所述传感器节点分组阶段将所需覆盖的传感器节点划分为独立的分组；
所述局部部署阶段在各个独立的分组中进行中继节点部署，最终的中继节点部署由各个分组的局部部署结果组成；
二次1-覆盖：对首次1-覆盖结果中只被一个中继节点覆盖的传感器节点进行二次1-覆盖；
将二次1-覆盖结果与首次1-覆盖所得到的结果进行合并，输出合并后的最终结果；
所述中继节点候选位置构建阶段包括以下步骤：
(1)输入所需覆盖的n个传感器节点位置信息X＝{x1,x2,…,xn}；
(2)i从1开始，标记xi为已搜索节点，构造一个以xi节点的物理位置为圆心，通信半径r为半径的圆，并在圆周上每隔 弧度取一个点，一个圆周共取k个点Y＝{y1,y2,…,yk}；
(3)从y1点开始，按照顺时针或者逆时针顺序，依次搜索以yj点(j＝1,2…k)的物理位置为圆心，通信半径r为半径的圆所能覆盖的传感器节点；
(4)取步骤(3)中至少覆盖两个传感器节点的点作为中继节点候选位置，记为集合P＝{p1,p2,…,pm}；
(5)标记X中的第i+1个传感器节点为已搜索节点，重复步骤(2)-(4)，并存储每次搜索到的候选位置P＝P∪Pi，直到X中所有传感器节点都标记为已搜索，并输出搜索结果P；所述Pi为中继节点候选位置的集合P中的元素，是步骤(3)中至少覆盖两个传感器节点的点。
2.根据权利要求1所述的面向双层结构无线传感器网络的中继节点鲁棒覆盖方法，其特征在于，所述步骤(4)中，如果k个点都只覆盖一个传感器节点，则选择距离基站最近的点作为中继节点候选位置Pi，其中pi表示yi的坐标，B表示基站的坐标。
3.根据权利要求1所述的面向双层结构无线传感器网络的中继节点鲁棒覆盖方法，其特征在于，所述传感器节点分组阶段包括以下步骤：
(1)从中继节点候选位置集合P中选择位置Pi：Pi覆盖最多的未被覆盖的传感器节点其中m表示集合P中元素个数，Z表示剩余传感器节点的集合；将所有被
Pi所覆盖的传感器节点组成的集合记为Si；
(2)将P中覆盖Si中传感器节点的中继节点候选位置的集合记为Ni，并将被Ni覆盖的传感器节点组成的集合称为Ti，将集合Si与集合Ti中所有的传感器节点统称为一个属于位置Pi的分组Gi；
(3)重复步骤(1)-(2)，存储每次的分组信息G＝G∪Gi，直到所有传感器节点都被分配至某一分组，并输出分组结果G。
4.根据权利要求1所述的面向双层结构无线传感器网络的中继节点鲁棒覆盖方法，其特征在于，所述局部部署阶段包括以下步骤：
(1)从G中依次选取属于位置Pi的分组Gi，从P中搜寻所有覆盖Gi中传感器节点的中继节点候选位置Fi，将几何圆盘覆盖问题就转换为最小集覆盖问题；
(2)使用贪婪算法，从Fi中搜索出(Gi-Si)的一个最小集覆盖MSCi，Pi的权重定义为wi＝|C|，其中C为Ni中未被MSCi覆盖的中继节点候选位置；如果wi>0，则选择MSCi与Pi作为局部部署结果；如果wi＝0且Pi中含有只被Pi覆盖的传感器节点，则选择MSCi与Pi作为局部部署结果；如果wi＝0且Pi中含没有只被Pi覆盖的传感器节点，则选择MSCi作为局部部署结果；记录本次本地搜索结果为Yi；
(3)重复步骤(1)-(2)，搜索Gi+1，存储对每个分组的最小集覆盖，即Y＝Y∪Yi，直到每个组中的传感器节点都被覆盖，输出最终搜索结果Y。
5.根据权利要求1所述的面向双层结构无线传感器网络的中继节点鲁棒覆盖方法，其特征在于，所述二次1-覆盖阶段包括以下步骤：
(1)从首次1-覆盖结果中挑选出只被一个中继节点覆盖的传感器节点X'＝{x'1,x'2,…,x'l}，1≤l≤n；
(2)根据应用于不同场合的无线传感器网络对于网络性能要求，人为调整中继节点的阈值H使得 其中m为中继节点候选位置构建阶段输出中继节点候选位置总数，阈值H为一个中继节点所能覆盖的传感器节点数量上限；
(3)利用面向1-覆盖的本地搜索方法LSAA对(1)所选择的传感器节点进行1-覆盖，从而使得所有传感器节点被至少两个中继节点所覆盖；
(4)本次覆盖结果D与首次1-覆盖所得到的结果进行合并，即T＝Y∪D，输出合并后的最终结果T。

面向双层结构无线传感器网络的中继节点鲁棒覆盖方法\n技术领域\n[0001] 本发明涉及无线传感器网络技术，具体地说是一种面向双层结构无线传感器网络的中继节点鲁棒覆盖方法。\n背景技术\n[0002] 无线传感器网络由低成本、低能耗的传感器节点组成，完成信息感知、简单数据处理以及短距离通信等功能。由于无线传感器网络在战场监视、环境监控、工业自动化、农业生产等方面的巨大应用潜力，一直以来都是研究的热点。但是传感器节点通常由电池供电，一经部署则难于更换，限制了无线传感器网络的寿命。现有技术中针对延长网络寿命的问题，提出一种双层的无线传感器网络结构。双层结构的网络中部署了少量的具有充足能源和较大通信半径的中继节点，扮演簇首的角色；1-跳邻居传感器节点将采集到的数据发送给中继节点，中继节点收集1-跳邻居传感器节点采集到的数据，并转发到汇聚节点。在采用双层结构的无线传感器网络中，传感器节点能够以节能方式转发采集到的信息。显然，中继节点在双层结构的无线传感器网络中至关重要。然而，中继节点成本较高，如何在保证网络网络覆盖及连通的前提下，降低中继节点部署成本(减少中继节点数量)成为目前的一个研究热点。\n[0003] 现有针对中继节点的部署方法包括几何单位圆覆盖阶段和网络连通性构建两类。\n其中，几何单位圆覆盖算法主要包括基于划分移动的方式、基于网格的方式、基于集覆盖的方式。基于划分移动方式的算法复杂度随着划分移动因子呈指数增长趋势；基于网格方式与基于集覆盖方式的算法，最终结果会部署较多的中继节点。总之，目前几何单位圆覆盖算法的计算复杂度较高，部署成本较高。\n[0004] 虽然无线传感器网络设计过程受限于成本因素，但是网络鲁棒性仍然是无线传感器网络设计的一个至关重要的问题。因此常规方法是采用对传感器节点进行2-覆盖的策略，即每个传感器节点至少被两个中继节点覆盖。传统的2-覆盖设计在1-覆盖的基础上，对少于被两个中继节点覆盖的传感器节点，仅仅使用1-覆盖算法进行简单地再次覆盖。\n发明内容\n[0005] 针对无线传感器网络2-覆盖算法设计过程中缺乏对中继节点部署数量、网络负载平衡、网络鲁棒性的综合考虑所导致的鲁棒性和最优性差等问题，本发明提出了一种面向双层结构无线传感器网络的中继节点鲁棒覆盖方法。\n[0006] 本发明为实现上述目的所采用的技术方案是：一种面向双层结构无线传感器网络的中继节点鲁棒覆盖方法，包括以下步骤：\n[0007] 首次1-覆盖：包括中继节点候选位置构建阶段、传感器节点分组阶段和局部部署阶段；所述中继节点候选位置构建阶段根据所需覆盖的传感器节点方位信息，构建全部中继节点的候选部署方位；所述传感器节点分组阶段将所需覆盖的传感器节点划分为独立的分组；所述局部部署阶段在各个独立的分组中进行中继节点部署，最终的中继节点部署由各个分组的局部部署结果组成；\n[0008] 二次1-覆盖：对首次1-覆盖结果中只被一个中继节点覆盖的传感器节点进行二次\n1-覆盖；\n[0009] 将二次1-覆盖结果与首次1-覆盖所得到的结果进行合并，输出合并后的最终结果。\n[0010] 所述中继节点候选位置构建阶段包括以下步骤：\n[0011] (1)输入所需覆盖的n个传感器节点位置信息X＝{x1,x2,…,xn}；\n[0012] (2)i从1开始，标记xi为已搜索节点，构造一个以xi节点的物理位置为圆心，通信半径r为半径的圆，并在圆周上每隔 弧度取一个点，一个圆周共取k个点Y＝{y1,y2,…,yk}；\n[0013] (3)从y1点开始，按照顺时针或者逆时针顺序，依次搜索以yj点(j＝1,2…k)的物理位置为圆心，通信半径r为半径的圆所能覆盖的传感器节点；\n[0014] (4)取步骤(3)中至少覆盖两个传感器节点的点作为中继节点候选位置，记为集合P＝{p1,p2,…,pm}；\n[0015] (5)标记X中的第i+1个传感器节点为已搜索节点，重复步骤(2)-(4)，并存储每次搜索到的候选位置P＝P∪Pi，直到X中所有传感器节点都标记为已搜索，并输出搜索结果P。\n[0016] 所述步骤(4)中，如果k个点都只覆盖一个传感器节点，则选择距离基站最近的点作为中继节点候选位置Pi，其中pi表示yi的坐标，B表示基站的坐标。\n[0017] 所述传感器节点分组阶段包括以下步骤：\n[0018] (1)从中继节点候选位置集合P中选择位置Pi：Pi覆盖最多的未被覆盖的传感器节点 其中m表示集合P中元素个数，Z表示剩余传感器节点的集合；将所有\n被Pi所覆盖的传感器节点组成的集合记为Si；\n[0019] (2)将P中覆盖Si中传感器节点的中继节点候选位置的集合记为Ni，并将被Ni覆盖的传感器节点组成的集合称为Ti，将集合Si与集合Ti中所有的传感器节点统称为一个属于位置Pi的分组Gi；\n[0020] (3)重复步骤(1)-(2)，存储每次的分组信息G＝G∪Gi，直到所有传感器节点都被分配至某一分组，并输出分组结果G。\n[0021] 所述局部部署阶段包括以下步骤：\n[0022] (1)从G中依次选取属于位置Pi的分组Gi，从P中搜寻所有覆盖Gi中传感器节点的中继节点候选位置Fi，将几何圆盘覆盖问题就转换为最小集覆盖问题；\n[0023] (2)使用贪婪算法，从Fi中搜索出(Gi-Si)的一个最小集覆盖MSCi，Pi的权重定义为wi＝|C|，其中C为Ni中未被MSCi覆盖的中继节点候选位置；如果wi>0，则选择MSCi与Pi作为局部部署结果；如果wi＝0且Pi中含有只被Pi覆盖的传感器节点，则选择MSCi与Pi作为局部部署结果；如果wi＝0且Pi中含没有只被Pi覆盖的传感器节点，则选择MSCi作为局部部署结果；记录本次本地搜索结果为Yi；\n[0024] (3)重复步骤(1)-(2)，搜索Gi+1，存储对每个分组的最小集覆盖，即Y＝Y∪Yi，直到每个组中的传感器节点都被覆盖，输出最终搜索结果Y。\n[0025] 所述二次1-覆盖阶段包括以下步骤：\n[0026] (1)从首次1-覆盖结果中挑选出只被一个中继节点覆盖的传感器节点X'＝{x'1,x'2,…,x'l}，1≤l≤n；\n[0027] (2)根据应用于不同场合的无线传感器网络对于网络性能要求，人为调整中继节点的阈值H使得 其中m为中继节点候选位置构建阶段输出中继节点候选位\n置总数，阈值H为一个中继节点所能覆盖的传感器节点数量上限；\n[0028] (3)利用面向1-覆盖的本地搜索方法LSAA对(1)所选择的传感器节点进行1-覆盖，从而使得所有传感器节点被至少两个中继节点所覆盖；\n[0029] (4)本次覆盖结果D与首次1-覆盖所得到的结果进行合并，即T＝Y∪D，输出合并后的最终结果T。\n[0030] 本发明提出的一种面向双层结构无线传感器网络的中继节点鲁棒覆盖方法，是在充分考虑双层结构的无线传感器网络应用的特殊性前提下提出的，该方法能够有效地降低中继节点部署成本，并保证所需的负载平衡、鲁棒性等网络性能。具体表现在：\n[0031] 1.本发明在考虑中继节点部署数量、网络负载平衡、网络鲁棒性的基础上，首先对节点进行分组，将全局覆盖问题降解到局部覆盖问题，降低问题求解复杂度；然后进行首次\n1-覆盖；二次1-覆盖针对每个分组，在调整算法的阈值后，使用1-覆盖算法进行覆盖；从而在保证覆盖鲁棒性的同时实现了中继节点最优部署。\n[0032] 2.本发明提出的首次1-覆盖，通过将所需覆盖的传感器节点划分为独立的不同分组，将部署问题从整体降解到局部，从而有效地减少所需部署中继节点的数量以及方法求解时间；\n[0033] 3.本发明提出的二次1-覆盖，针对每个分组，通过调整中继节点阈值，改变部署中继节点数量、网络负载平衡、鲁棒性等特性，从而有效地改善网络性能。\n附图说明\n[0034] 图1为中继节点候选位置构建示意图；\n[0035] 图2为传感器节点分组示意图；\n[0036] 图3为中继节点局部部署示意图；\n[0037] 图4为阈值对中继节点部署数量的影响；\n[0038] 图5为阈值对传感器节点被覆盖次数影响；\n[0039] 图6为阈值对中继节点所覆盖传感器节点数量影响；\n[0040] 图7为一个最终输出结果示意图。\n具体实施方式\n[0041] 下面结合附图及实施例对本发明做进一步的详细说明。\n[0042] 本发明提出的一种面向双层结构无线传感器网络的中继节点鲁棒覆盖方法，其主要思想在于：在考虑中继节点部署数量、网络负载平衡、网络鲁棒性的基础上，通过将所需覆盖的传感器节点划分为独立的不同分组进行首次1-覆盖；然后针对每个分组，在调整算法的阈值后，在此使用1-覆盖算法进行覆盖；以确保无线传感器网络对于中继节点部署数量、负载平衡、鲁棒性等网络性能的要求。\n[0043] 本发明方法包括首次1-覆盖与二次1-覆盖两个步骤。\n[0044] 步骤(1)首次1-覆盖，包括中继节点候选部位置构建阶段、传感器节点分组阶段以及局部部署阶段，具体包括以下步骤：\n[0045] (1.1)中继节点候选部位置构建阶段如图1所示：\n[0046] (1.1.1)输入所需覆盖的传感器节点位置信息X＝{x1,x2,x3,x4,x5,x6,x7,x8,x9}；\n[0047] (1.1.2)标记传感器节点x1为已搜索节点；\n[0048] (1.1.3)构造x1为圆心，通信半径r为半径的圆，并在其圆周上均匀取4个点，依次搜寻4个点所能覆盖的传感器节点，取其中至少覆盖两个传感器节点的点作为中继节点候选位置，如果4个点都只覆盖一个传感器节点，则选择距离基站最近的点作为中继节点候选位置；x1上的候选位置分别为P2＝{x1,x7,x8,x9},P3＝{x1,x4,x5,x6,x7},P2＝{x1,x2,x3,x4}；\n[0049] (1.1.4)重复(1.1.2)-(1.1.3)，直到X＝{x1,x2,x3,x4,x5,x6,x7,x8,x9}全部标记为已搜索节点。\n[0050] (1.2)传感器节点分组阶段如图2所示：\n[0051] (1.2.1)在中继节点候选位置中选择位置Pi：该位置覆盖最多的未被覆盖的传感器节点。将所有被位置Pi所覆盖的传感器节点组成的集合称为Si。图2中标记为V的圆即为Pi所覆盖的范围，其中标记为V的圆内的点即为Si；\n[0052] (1.2.2)将P中覆盖Si中传感器节点的中继节点候选位置的集合记为Ni，并将被Ni覆盖的传感器节点组成的集合称为Ti，将集合Si与集合Ti中所有的传感器节点统称为一个属于位置Pi的分组Gi。图2中，标记为K的圆即为Ni，其中在标记为K的圆内，不属于标记为V的圆内的点即为Ti，标记为V的圆与标记为K的圆内的点共同组成了一个分组Gi；\n[0053] (1.2.3)重复(1.2.1)-(1.2.2)直到所有传感器节点都被分配至某一分组。\n[0054] (1.3)局部部署分组阶段如图3所示：\n[0055] (1.3.1)从G中依次(从1开始)选取属于位置Pi的分组Gi，从P中搜寻所有覆盖Gi中传感器节点的中继节点候选位置Fi，将几何圆盘覆盖GDC问题就转换为最小集覆盖MSC问题；\n[0056] (1.3.2)使用贪婪算法，从Fi中搜索出(Gi-Si)的一个最小集覆盖MSCi，Pi的权重定义为wi＝|C|，其中C为Ni中未被MSCi覆盖的中继节点候选位置；如果wi>0，则选择MSCi与Pi作为局部部署结果；如果wi＝0且Pi中含有只被Pi覆盖的传感器节点，则选择MSCi与Pi作为局部部署结果；如果wi＝0且Pi中含没有只被Pi覆盖的传感器节点，则选择MSCi作为局部部署结果；记录本次本地搜索结果为Yi；图3中，标记为V的圆即为Pi，其中标记为W的圆表示MSCi，可以看出Ni中尚有一个位置未被MSCi覆盖，所以其权重wi＝1>0，因此选择MSCi与Pi作为局部部署结果，即选择标记为W的圆与标记为V的圆为本次局部部署结果；\n[0057] (1.3.3)重复(1.3.1)-(1.3.3)，搜索Gi+1，存储对每个分组的最小集覆盖，即Y＝Y∪Yi，直到每个组中的传感器节点都被覆盖，输出最终搜索结果Y。\n[0058] 步骤(2)二次1-覆盖阶段，具体包括以下步骤：\n[0059] (2.1)从首次1-覆盖结果中挑选出只被一个中继节点覆盖的传感器节点X'＝{x'1,x'2,…,x'k},(1≤k≤n)；\n[0060] (2.2)根据无线传感器网络对于中继节点部署数量、网络负载平衡、网络鲁棒性等网络性能要求，人为调整中继节点的阈值H，使得 其中m为中继节点候选位置总数；该阈值代表了每个中继节点候选位置所能覆盖的传感器节点数量上限。图4-图6表示阈值对中继节点部署数量的影响、阈值对传感器节点被中继节点覆盖的次数的影响、阈值对中继节点所覆盖传感器节点数量的影响；根据特定网络环境对性能的要求调整阈值H，保证良好的网络性能；\n[0061] (2.3)利用首次1-覆盖的本地搜索方法对(2.1)所选择的传感器节点进行1-覆盖，从而使得所有传感器节点被至少两个中继节点所覆盖；\n[0062] (2.4)本次覆盖结果D与首次1-覆盖所得到的结果进行合并，即T＝Y∪D，输出合并后的最终结果T。\n[0063] 图7为一个最终输出结果示意图，其中，-分组划分所使用的不规则封闭曲线表示对传感器节点的分组。可以看出分组内的每个传感器节点都至少被两个中继节点覆盖，因此中继节点的故障对整个网络的影响减小，从而提高了网络的鲁棒性，其中标记为1的圆为\n1-覆盖输出中继节点的覆盖范围，标记为2的圆为2-覆盖输出中继节点的覆盖范围。同时每个中继节点所覆盖的传感器节点数量不能超过设定的阈值，因此本发明所提出的方法可以在提高无线传感器网络鲁棒性的基础上进一步保证负载平衡。