基于布尔搜索的空间目标分布最小包围盒规划

Smallest Enclosing Rectangle Planning for Spatial Target Distribution on the Basis of Boolean Search

为了降低对平面内无源目标进行定位产生的搜索代价,研究了确定覆盖所有随机部署的无线传感器网络节点的最小包围盒问题.首先提出基于布尔搜索的无线传感器网络节点最小包围盒规划方法,运用深度优先策略,使锚节点不断逼近目标节点的实际位置;然后根据前述算法完成时的锚节点坐标,设计了坐标最大-最小值规划算法以构造最小覆盖面积包围盒.最后通过仿真和算法分析得出,所提策略计算复杂度低于遍历方式的最小包围圆、包围盒算法,且能更准确地估计出覆盖面积最小的包围盒.

In order to save the searching cost of passive target location in two-dimension planes,a smallest enclosing rectangle problem for randomly-deployed WSN（ Wireless Sensor Network） nodes is investigated. Firstly,a smallest enclosing rectangle planning method for WSN nodes,which makes anchors continuously approach target nodes with the depth-first searching strategy,is proposed on the basis of Boolean search. Then,a coordinate maxmin algorithm is put forward to compute the minimum enclosing rectangle according to aforementioned anchors＇ location. The results of both simulation and algorithm analysis show that the proposed strategy possesses less computation complexity than such searching strategies as traversal methods for smallest enclosing rectangle and circle,and helps obtain the enclosing rectangle with minimum area more precisely.