论文部分内容阅读
[摘 要]以无人机组网监测为背景，为提高监测质量并延长寿命，将问题转化为负载均衡剖分问题，在确保无监测漏洞的前提下，基于Voronoi剖分和梯度法，提出一种分布式控制算法。针对非均匀的负载权值函数，采用基于逆函数法定义一种新的广义Voronoi图剖分。相比传统的Voronoi质心算法，部署结果明显更为均衡。
[关键词]负载均衡，移动传感器，Voronoi图，无人机组网
中图分类号：TP13 文献标识码：B 文章编号：1009-914X（2014）31-0305-01
1 引言
随着电子技术的持续快速发展，各类监测跟踪传感器如雷达、无人机等都朝着个体功能多元化，群体网络化、规模化方向发展。传感器组网使得大范围高动态监测成为可能[1-2]。网内各传感器的部署好坏，直接影响监测跟踪性能。
在无人机监测应用中，各无人机在监测区内巡航并作信息融合。为保证任务并行高效，首先就是对整个监测区进行划分，指派给每个无人机 [3]。因此讨论负载均衡的传感器部署，有很大的实际意义。
现有均衡剖分算法多数为集中式算法，不适合大规模传感器网络。Pavone等基于power图，讨论固定节点的负载均衡分布式算法[3]。算法扩展性好，但其未考虑节点监测、通信范围受限的情况。在[4]中，作者提出一种分布式任务均衡剖分算法，但在非均匀分布密度函数时，最优剖分不一定存在，本文通过建立基于逆函数法定义广义Voronoi剖分来解决此问题。
2 定义及问题描述
记网络内节点的Voronoi剖分为，其Voronoi邻居记为，有效监测集。节点的负载定义为。
建立如下目标函数：min （1）
s.t. （2）
3 分布式优化算法
3.1 均匀分布密度函数
分布密度函数均匀时，控制律为
（3）
其中其中，为惩罚因子，
（4）
具体推导及更多定义，可参见文献[4]。
3.2 非均匀分布密度函数
当分布密度函数非均匀时，严格的均衡剖分不一定存在[5]。可定义如下广义Voronoi剖分，结合控制律求得非均密度下的均衡剖分。
定义4 （广义Voronoi剖分） 对，映射，剖分称为广义Voronoi剖分，其中：
（5）
具体算法步骤为：
（1） 初始化；
（2） 获取单跳邻居节点相对位置等信息；
（3） 获取或估计分布密度函数并计算广义Voronoi剖分；
（4） 将Voronoi剖分及所有邻居节点位置信息映射到镜像区；
（5） 在镜像区内基于均匀权值的剖分算法求得控制量；
（6） 将控制量映射回原区域并执行控制指令；
（7） 检验是否满足终止条件，若满足，则重新计算广义Voronoi剖分并结束，否则转步骤（2）。
本文提出两个分布式映射。
一是分布密度函数在和轴方向上独立，变换为：
（6）
其中=arg，
二是分布密度函数关于某点对称，此时，存在，其中
（7）
此时，令变换 （8）
其中 （9）
4 仿真研究
（a） 初始分布 （b） 部署结果
图1 基于广义Voronoi剖分的负载均衡部署
控制律有效性已经在[4]中验证，只需验证基于广义Voronoi图非均匀分布密度下的剖分算法的有效性。10个节点的初始随机分布如图1（a）。分布密度函数，，。部署结果如图1（b），负载偏差，其中为负载平均值，由此可见算法能有效平衡各节点负载。
5 结束语
本文讨论了网络监测中的负载均衡剖分问题。针对非均匀分布密度函数情况，提出了一种新的广义Voronoi剖分，确保均衡剖分的存在性。与传统Voronoi质心算法相比，负载明显更加均衡。
参考文献（References）
[1] Le Ny， Jerome， and George J. Pappas. "Adaptive deployment of mobile robotic networks."？Automatic Control， IEEE Transactions on？58.3 （2013）： 654-666.
[2] 涂志亮，王强，沈毅。 "移动传感器网络中目标跟踪与监测的同步优化."？自动化学报？38.3 （2012）： 452-461.
[3] Pavone M， Frazzoli E， Bullo， F. Adaptive and Distributed Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment[J]. IEEE Trans on Automatic Control， 2011， 56（6）：1259 – 1274.
[4] 沈毅， 涂志亮， 王强. 一种分布式移动传感器负载均衡部署算法[J]. 控制工程， 2012， 19（006）： 1051-1054.
[5] Pavone M， Arsie A， Frazzoli E， Bullo F. Distributed algorithms for environment partitioning in mobile robotic networks[J]. IEEE Trans on Automatic Control， 2011， 56（8）： 1834-1848.
作者简介
涂志亮 男，1983年生于湖北孝感，工程师，博士，控制科学与工程专业，主要研究方向为雷达总体设计、传感器网络优化部署、多智能体分布式控制。
[关键词]负载均衡，移动传感器，Voronoi图，无人机组网
中图分类号：TP13 文献标识码：B 文章编号：1009-914X（2014）31-0305-01
1 引言
随着电子技术的持续快速发展，各类监测跟踪传感器如雷达、无人机等都朝着个体功能多元化，群体网络化、规模化方向发展。传感器组网使得大范围高动态监测成为可能[1-2]。网内各传感器的部署好坏，直接影响监测跟踪性能。
在无人机监测应用中，各无人机在监测区内巡航并作信息融合。为保证任务并行高效，首先就是对整个监测区进行划分，指派给每个无人机 [3]。因此讨论负载均衡的传感器部署，有很大的实际意义。
现有均衡剖分算法多数为集中式算法，不适合大规模传感器网络。Pavone等基于power图，讨论固定节点的负载均衡分布式算法[3]。算法扩展性好，但其未考虑节点监测、通信范围受限的情况。在[4]中，作者提出一种分布式任务均衡剖分算法，但在非均匀分布密度函数时，最优剖分不一定存在，本文通过建立基于逆函数法定义广义Voronoi剖分来解决此问题。
2 定义及问题描述
记网络内节点的Voronoi剖分为，其Voronoi邻居记为，有效监测集。节点的负载定义为。
建立如下目标函数：min （1）
s.t. （2）
3 分布式优化算法
3.1 均匀分布密度函数
分布密度函数均匀时，控制律为
（3）
其中其中，为惩罚因子，
（4）
具体推导及更多定义，可参见文献[4]。
3.2 非均匀分布密度函数
当分布密度函数非均匀时，严格的均衡剖分不一定存在[5]。可定义如下广义Voronoi剖分，结合控制律求得非均密度下的均衡剖分。
定义4 （广义Voronoi剖分） 对，映射，剖分称为广义Voronoi剖分，其中：
（5）
具体算法步骤为：
（1） 初始化；
（2） 获取单跳邻居节点相对位置等信息；
（3） 获取或估计分布密度函数并计算广义Voronoi剖分；
（4） 将Voronoi剖分及所有邻居节点位置信息映射到镜像区；
（5） 在镜像区内基于均匀权值的剖分算法求得控制量；
（6） 将控制量映射回原区域并执行控制指令；
（7） 检验是否满足终止条件，若满足，则重新计算广义Voronoi剖分并结束，否则转步骤（2）。
本文提出两个分布式映射。
一是分布密度函数在和轴方向上独立，变换为：
（6）
其中=arg，
二是分布密度函数关于某点对称，此时，存在，其中
（7）
此时，令变换 （8）
其中 （9）
4 仿真研究
（a） 初始分布 （b） 部署结果
图1 基于广义Voronoi剖分的负载均衡部署
控制律有效性已经在[4]中验证，只需验证基于广义Voronoi图非均匀分布密度下的剖分算法的有效性。10个节点的初始随机分布如图1（a）。分布密度函数，，。部署结果如图1（b），负载偏差，其中为负载平均值，由此可见算法能有效平衡各节点负载。
5 结束语
本文讨论了网络监测中的负载均衡剖分问题。针对非均匀分布密度函数情况，提出了一种新的广义Voronoi剖分，确保均衡剖分的存在性。与传统Voronoi质心算法相比，负载明显更加均衡。
参考文献（References）
[1] Le Ny， Jerome， and George J. Pappas. "Adaptive deployment of mobile robotic networks."？Automatic Control， IEEE Transactions on？58.3 （2013）： 654-666.
[2] 涂志亮，王强，沈毅。 "移动传感器网络中目标跟踪与监测的同步优化."？自动化学报？38.3 （2012）： 452-461.
[3] Pavone M， Frazzoli E， Bullo， F. Adaptive and Distributed Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment[J]. IEEE Trans on Automatic Control， 2011， 56（6）：1259 – 1274.
[4] 沈毅， 涂志亮， 王强. 一种分布式移动传感器负载均衡部署算法[J]. 控制工程， 2012， 19（006）： 1051-1054.
[5] Pavone M， Arsie A， Frazzoli E， Bullo F. Distributed algorithms for environment partitioning in mobile robotic networks[J]. IEEE Trans on Automatic Control， 2011， 56（8）： 1834-1848.
作者简介
涂志亮 男，1983年生于湖北孝感，工程师，博士，控制科学与工程专业，主要研究方向为雷达总体设计、传感器网络优化部署、多智能体分布式控制。