确定至少需要放置多少个节点,才能覆盖95%以上的区域?

在一个监视区域为边长b=100(长度单位)的正方形中,每个节点的覆盖半径均为r=10(长度单位)。在设计传感网络时,需要知道对给定监视区域在一定的覆盖保证下应放置节点的最少数量。对于上述给定的监视区域及覆盖半径,确定至少需要放置多少个节点,才能覆盖95%以上的区域?
关注者
140
被浏览
5533

6 个回答

写个智能粒子群算法算一下就有了。
当年帮老板写教材用得就是这个经典问题。
这是一个非常经典的circle packing问题,一直没想过还有这样的变形,但是觉得还挺有实际意义的。理论下限是33。

circle packing原始问题是在一个平面里堆一样大小的圆,怎么堆能覆盖率最大,圆之间不能有重合。各种乱排可以如下面的左图,也可以如右图。

著名的拉格朗日1773年就证明了右图的排法是最高效的排法[1],

换成六边形的范围来理解,这样的结构可以无限延伸,所以用这种方法的覆盖率是,


\eta_h = \frac{\pi}{2\sqrt3}  \approx 0.9069

显然如果没有重合,这种牛逼的排法,还是无法达到95%的要求。
接下来就必须要有重合了。
重合可以这样,这是当两个圆重合部分最宽的地方等于 0.28*r 时。六边形内的覆盖率为100%,r为小圆的半径。
也可以这样,这是当两个圆重合部分最宽的地方等于0.08*r 时,这样的覆盖率是 0.9559。
如果面积非常大,不需要考虑边界问题的话,只需要这样一直堆六边形就可以无限堆下去了,


平均下来,需要3个圆来覆盖这样一个六边形。六边形的半径是 1.92 * r, 因此六边形的面积为:area = \frac{3\sqrt3}{2} \times (1.92r)^2
需要圆的个数是 \frac{total\_area}{area} \times 3

r=10时, area = 957.75,边长为100的正方形面积10^4, 需要10.44个六边形,也就是11个六边形.
这样需要圆个数的下限是:33个。因为边界处利用率较低,实际数字要大于等于33。


代码在 nbviewer.ipython.org/gi
=================================

当考虑边界问题的时候,两个圆重合部分最宽的地方等于0.08*半径不一定是最优解,因为边缘地区用这样的六边形来填充不怎么实惠。

呃。。。考虑边界的代码还没写完。。
为什么?