基于布爾搜索的空間目標(biāo)分布最小包圍盒規(guī)劃*

衛(wèi)星　韓江洪

(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院∥教育部安全關(guān)鍵工業(yè)測(cè)控工程研究中心,安徽 合肥 230009)

?

基于布爾搜索的空間目標(biāo)分布最小包圍盒規(guī)劃*

衛(wèi)星韓江洪

(合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院∥教育部安全關(guān)鍵工業(yè)測(cè)控工程研究中心,安徽 合肥 230009)

摘要:為了降低對(duì)平面內(nèi)無(wú)源目標(biāo)進(jìn)行定位產(chǎn)生的搜索代價(jià)，研究了確定覆蓋所有隨機(jī)部署的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的最小包圍盒問(wèn)題.首先提出基于布爾搜索的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)最小包圍盒規(guī)劃方法，運(yùn)用深度優(yōu)先策略，使錨節(jié)點(diǎn)不斷逼近目標(biāo)節(jié)點(diǎn)的實(shí)際位置；然后根據(jù)前述算法完成時(shí)的錨節(jié)點(diǎn)坐標(biāo)，設(shè)計(jì)了坐標(biāo)最大-最小值規(guī)劃算法以構(gòu)造最小覆蓋面積包圍盒.最后通過(guò)仿真和算法分析得出，所提策略計(jì)算復(fù)雜度低于遍歷方式的最小包圍圓、包圍盒算法，且能更準(zhǔn)確地估計(jì)出覆蓋面積最小的包圍盒.

關(guān)鍵詞：無(wú)線(xiàn)定位；最小包圍盒；覆蓋圓；凸殼規(guī)劃

在一些事故場(chǎng)景中，存在大量的目標(biāo)物體需要被定位.例如，飛機(jī)的殘骸碎片、戰(zhàn)后遺棄的地雷、甚至是放射性的核泄漏物等.與通常的目標(biāo)定位不同，它們大多是隨機(jī)散落在一片空間內(nèi)，都是無(wú)源的，無(wú)法通過(guò)測(cè)量目標(biāo)與參照物之間的距離估計(jì)其位置坐標(biāo)[1].對(duì)于類(lèi)似的被動(dòng)目標(biāo)定位，劃分出一塊面積盡可能小的搜索范圍，直接決定了目標(biāo)定位所需要花費(fèi)的代價(jià)[2].

目前，以位置指紋匹配法為代表的諸多定位方法，均以目標(biāo)位置與場(chǎng)景特征形成的一對(duì)一映射作為定位的先驗(yàn)條件[3- 5]，這些方法都需要事先劃分覆蓋所有目標(biāo)的規(guī)則形狀.如此，最小覆蓋面的劃分問(wèn)題就轉(zhuǎn)化為包含全部目標(biāo)的最小包圍形狀的規(guī)劃問(wèn)題[6- 7].在計(jì)算幾何領(lǐng)域，研究最小包圍形狀的算法很多，經(jīng)典的包括最小包圍圓規(guī)劃和最小包圍盒規(guī)劃[8- 9].其中，最小包圍盒是一種覆蓋面積最小的規(guī)則矩形，其規(guī)劃算法的復(fù)雜度小于最小包圍圓，廣泛用于碰撞檢測(cè)、模具分形設(shè)計(jì)與模式識(shí)別[10].

在目標(biāo)坐標(biāo)未知情況下，根據(jù)深度優(yōu)先搜索策略，文中提出了布爾搜索的錨節(jié)點(diǎn)位置規(guī)劃算法，通過(guò)局部覆蓋目標(biāo)分布的外圍區(qū)域，使得錨節(jié)點(diǎn)深度遍歷過(guò)程中，不斷迭代逼近外圍的目標(biāo).根據(jù)迭代完成時(shí)的錨節(jié)點(diǎn)坐標(biāo)，設(shè)計(jì)了坐標(biāo)最大-最小值規(guī)劃算法，構(gòu)造了覆蓋面積接近最小的包圍盒.

1問(wèn)題描述

給定長(zhǎng)寬均為L(zhǎng)的矩形區(qū)域Ω，其4個(gè)頂點(diǎn)的直角坐標(biāo)分別為O(0,0)、B(0,L)、C(L,L)和D(L,0).n個(gè)目標(biāo)物構(gòu)成的平面點(diǎn)集S分布在Ω內(nèi)，S={s1,s2，…,sn}.?si∈S的坐標(biāo)值以均勻分布的隨機(jī)方式產(chǎn)生，si=(Lθi,1,Lθi,2)，θi,1,θi,2～N(0,1),表示極角.n≥3時(shí)，根據(jù)S構(gòu)成的凸殼頂點(diǎn)BCH(S′)為一個(gè)凸多邊形G，G的頂點(diǎn)均來(lái)自S.令P為包圍S的最小凸多邊形，即不存在凸多邊形P′，使得P?P′?S成立.

(a)軸向矩形包圍盒

(b)定向矩形包圍盒

2布爾搜索的錨節(jié)點(diǎn)部署

通過(guò)錨節(jié)點(diǎn)的信號(hào)接收范圍，構(gòu)建相應(yīng)的覆蓋圓，實(shí)現(xiàn)Ω局部區(qū)域的覆蓋，完成S凸殼頂點(diǎn)BCH(S)的搜索.

定義1錨節(jié)點(diǎn)i部署在a(i)點(diǎn)，其信號(hào)接收半徑為r(i),則i形成一個(gè)覆蓋圓，記作[a(i),r(i)].

如果錨節(jié)點(diǎn)i在覆蓋圓[a(i),r(i)]內(nèi)收到信號(hào)，則向Sink發(fā)送信息，表示至少存在一個(gè)目標(biāo)δ(i)∈S，使得[a(i),r(i)]將其包含.由于發(fā)送的信息被錨節(jié)點(diǎn)i量化為1比特的局部消息M(i)，

定義3設(shè)覆蓋圓a(i)和a(j)的中心距離為d(i,j)，d(i,j)=‖a(i)-a(j)‖2，如果d(i,j)

算法1A←Anchor array(ω,d,P)

輸出：A為規(guī)劃的覆蓋圓心坐標(biāo)集合；

ω為當(dāng)前的覆蓋圓心坐標(biāo)；

圖2　覆蓋圓的局部覆蓋

輸入：d為ω與相鄰覆蓋圓心的歐式距離；

P為凸多邊形，P?Ω；

過(guò)程:① 若(ω,d)沒(méi)有節(jié)點(diǎn)，轉(zhuǎn)向③；

② A←cover_search( ω，γ，γ/[2cos(/6)]) ;\子覆蓋圓規(guī)劃

④ 依次設(shè)v={α,β,T,J,Q,K}，如果v位于P內(nèi)，A←v；

⑤A←Anchor_array(v,d,P).

函數(shù)A←cover_search(ω,r,ρ)

輸出：A為覆蓋圓ω內(nèi)規(guī)劃的子覆蓋圓心坐標(biāo)

ω為覆蓋圓的中心；

輸入：r為ω的半徑；

ρ為子覆蓋圓ωi+1的半徑；

② 依次設(shè)ωi+1={α,β,T,J,Q,K},如果滿(mǎn)足(ωi+1,ρ)存在節(jié)點(diǎn)，(ωi+1,ρ)?(ω，r)，ρ>ζ，則A←ωi+1;

④A←cover_search(ωi+1,r,ρ).

為4個(gè)方向的出發(fā)點(diǎn).

圖3　局部覆蓋情況下搜尋外圍節(jié)點(diǎn)過(guò)程

Fig.3Node searching process under the circumstance of partial coverage

3坐標(biāo)最大-最小值的最小包圍盒規(guī)劃

A′的個(gè)數(shù)為m，存在a∈A′，以及?s?S，滿(mǎn)足‖a-s‖2≤ζ.首先，運(yùn)用Graham算法從A′提取構(gòu)成凸殼邊界BCH(A′)的頂點(diǎn)集合Π，凸殼頂點(diǎn)個(gè)數(shù)為η.根據(jù)Π的X坐標(biāo)的最小值min_X和最大值max_X，以及Y坐標(biāo)的最小值min_Y和最大值max_Y，建立頂點(diǎn)O(min_X,min_Y)、B(min_X,max_Y)、C(max_X,max_Y)和D(max_X,min_Y)，順序連接上述4個(gè)頂點(diǎn)，可以建立面積最小的軸向包圍盒ΣZ，如圖4所示.ΣZ的面積為S(ΣZ)，

|max_X-min_X||max_Y-min_Y|

(1)

圖4　最小覆蓋面積的軸向包圍盒

圖5　最小覆蓋面積的定向包圍盒

為S的最小包圍盒，i∈[1,2,…,η]，其算法如下.

算法2V←maxmin_coordinate(A′)

輸出：最小包圍盒Σ的頂點(diǎn)坐標(biāo)V；

輸入：A′覆蓋圓的中心集合；

過(guò)程：①P←graham(A′),采用Graham算法求出A′中的凸殼邊界頂點(diǎn)P；

② head←P(i)，rear←P(i+1)；rear在Ψ內(nèi)的極角為θ(i)；

③ 將Ψ的中心平移至head，再逆時(shí)針偏轉(zhuǎn)θ(i)，得到新的坐標(biāo)系Ψ(i);

④ 計(jì)算P在Ψ(i)的直角坐標(biāo)P(i)；

⑤ 從P(i)提取max_X、min_X、max_Y和max_Y；

⑥ 提取Ψ(i)下的定向包圍矩形Σ(i)的4個(gè)頂點(diǎn)，以順時(shí)針?lè)较颍篛(i)=(min_X,min_Y)，B(i)=(min_X,max_Y)，C(i)=(max_X,max_Y)，D(i)=(max_X,min_Y)；

4算法效率分析

文中通過(guò)比較覆蓋圓全覆蓋方法與算法1的效率，證明算法1的覆蓋圓部署代價(jià)小于一般性的方法.算法效率是指在給定的相同邊長(zhǎng)區(qū)域Ω和相同閾值ζ的情況下，滿(mǎn)足每個(gè)目標(biāo)至少被一個(gè)覆蓋圓布爾覆蓋時(shí)，算法輸出的最大覆蓋圓個(gè)數(shù).其中，算法1輸出的覆蓋圓半徑γ是變長(zhǎng)的，在布爾搜索過(guò)程中，隨著搜索深度的增加，γ逐漸減小，如定理1所示.

而一般的全覆蓋方法是不再規(guī)劃子覆蓋圓，所有輸出的覆蓋圓半徑均為閾值ζ.

由定理2可知，全覆蓋方法在搜索部署過(guò)程中，始終是以半徑r滿(mǎn)足小于等于ζ的覆蓋圓實(shí)現(xiàn)Ω的全覆蓋，該方法是固定尺度的搜索，與算法1的變尺度搜索策略相比，算法的時(shí)間復(fù)雜度低，且錨節(jié)點(diǎn)的感知半徑是固定的，輸出的覆蓋圓個(gè)數(shù)必然大于算法1.因此，如果錨節(jié)點(diǎn)的感知范圍在線(xiàn)性可調(diào)的情況下，算法1的算法效率明顯優(yōu)于全覆蓋方法.

5仿真實(shí)驗(yàn)與分析

采用Matlab 2013b作為仿真實(shí)驗(yàn)平臺(tái)，正方形區(qū)域Ω給定的長(zhǎng)寬均為100 m.根據(jù)算法1，對(duì)圖3所示區(qū)域進(jìn)行布爾搜索的錨節(jié)點(diǎn)部署.設(shè)定初始時(shí)的錨節(jié)點(diǎn)覆蓋圓半徑r=14.142 m，閾值ζ為2 m和3 m時(shí)，分別進(jìn)行12組仿真.每組仿真隨機(jī)生成的節(jié)點(diǎn)數(shù)為n，算法1產(chǎn)生的包含節(jié)點(diǎn)的覆蓋圓個(gè)數(shù)為E，全覆蓋方法包含節(jié)點(diǎn)的覆蓋圓個(gè)數(shù)為EA.算法2規(guī)劃的最小定向包圍盒面積為ΣD，最小軸向包圍盒面積為ΣZ.

圖6為固定節(jié)點(diǎn)個(gè)數(shù)n=100時(shí)覆蓋圓個(gè)數(shù)隨ζ的變化曲線(xiàn)，可見(jiàn)，閾值ζ越大，錨節(jié)點(diǎn)覆蓋圓個(gè)數(shù)E和EA越大.由圖7可知，隨著節(jié)點(diǎn)個(gè)數(shù)增加，覆蓋面積在初始階段呈現(xiàn)折線(xiàn)增長(zhǎng)的趨勢(shì)，節(jié)點(diǎn)個(gè)數(shù)增加到一定程度后，覆蓋面積的變化規(guī)律不明顯.由圖8可知：EA始終大于E；閾值ζ相同條件下，EA沒(méi)有隨著n的增加而遞增，而E則隨著n的增加而增大.這也驗(yàn)證了定理1所描述的，算法1的代價(jià)與n存在線(xiàn)性相關(guān).同時(shí)，n存在一個(gè)門(mén)限值ε，Ω面積為100 m2時(shí)，根據(jù)定理1和定理2計(jì)算得出：ζ=2 m時(shí)，ε=371;ζ=3 m時(shí)，ε=249；當(dāng)n>ε時(shí)，算法1的代價(jià)將超過(guò)全覆蓋方法.因此，節(jié)點(diǎn)密度較小時(shí)，適合運(yùn)用算法1的搜索策略.

圖6　覆蓋圓個(gè)數(shù)隨閾值的變化

Fig.6Changes of the number of cover circles with the increase of threshold

圖7　覆蓋面積隨節(jié)點(diǎn)個(gè)數(shù)的變化

圖8　覆蓋圓個(gè)數(shù)隨節(jié)點(diǎn)個(gè)數(shù)的變化

Fig.8Changes of the number of cover circles with the increase of nodes

根據(jù)分析遺漏的節(jié)點(diǎn)個(gè)數(shù)R可知，n較小時(shí)，ΣD遺漏的節(jié)點(diǎn)數(shù)較多；隨著n的增加，使得用于規(guī)劃ΣD的覆蓋圓個(gè)數(shù)E也增加，如果覆蓋圓分布的廣泛，則遺漏的節(jié)點(diǎn)數(shù)會(huì)下降.根據(jù)圖9數(shù)據(jù)分析得出，R由覆蓋圓分布的范圍決定.ΣD的面積越大，覆蓋圓的分布范圍也就越大，而E也就越高.如圖10所示，n=40時(shí)，算法2規(guī)劃的最小定向包圍盒為ΣD，最小軸向包圍盒為ΣZ.根據(jù)前述結(jié)果可知，ΣD在任何情況下的面積均小于或等于ΣZ.由于覆蓋圓的中心并非完全與S節(jié)點(diǎn)位置重合，所以ΣD之外仍存在少量的節(jié)點(diǎn).

圖9　遺漏節(jié)點(diǎn)數(shù)隨節(jié)點(diǎn)個(gè)數(shù)的變化

Fig.9Changes of the number of missed node with the increase of nodes

圖10　40個(gè)傳感節(jié)點(diǎn)規(guī)模的最小包圍盒

6結(jié)論

根據(jù)深度優(yōu)先搜索策略，實(shí)現(xiàn)了錨節(jié)點(diǎn)覆蓋圓對(duì)節(jié)點(diǎn)平面的局部覆蓋.隨著搜索深度的增加，不斷減小錨節(jié)點(diǎn)布爾感知范圍，使得產(chǎn)生的覆蓋圓中心點(diǎn)持續(xù)逼近節(jié)點(diǎn)的實(shí)際位置.仿真實(shí)驗(yàn)結(jié)果表明，基于DFS的布爾搜索得出的覆蓋圓中心坐標(biāo)，使得構(gòu)建的最小包圍盒僅將少量的節(jié)點(diǎn)排除在外.通過(guò)變換經(jīng)緯度坐標(biāo)系，根據(jù)提取的坐標(biāo)最大、最小值所獲得的包圍盒面積均小于坐標(biāo)系變換前的最小包圍盒面積.同時(shí)，在相同低密度節(jié)點(diǎn)分布的情況下，基于DFS的布爾搜索代價(jià)小于以往的全覆蓋方法.

參考文獻(xiàn)：

[1]SHRIVASTAVA N,MUDUMBAI R,MADHOW U,et al.Target tracking with binary proximity sensors [J].ACM Transactions on Sensor Networks,2009,5(4):1- 33.

[2]郭慶勝，馮代鵬，劉遠(yuǎn)剛.一種解算空間幾何對(duì)象的最小外接矩形算法 [J].武漢大學(xué)學(xué)報(bào)· 信息科學(xué),2014,39(2):177- 180.

GUO Qing-sheng,FENG Dai-peng,LIU Yuan-gang,et.al.An algorithm for computing the smallest-area enclosing rectangle of spatial geometric object(s) [J].Geomatics and Information Science of Wuhan University,2014,39(2):177- 180.

[3]ZHAO C,HEINZELMAN W B.Searching strategy for multi-target discovery in wireless networks [C]∥Proceedings of 4th Workshop on Applications and Services in Wireless Networks.Boston:IEEE,2004:1- 10.

[4]WANG H,SEN S,ELGOHARY A,et al.No need to war-drive:unsupervised indoor localization [C]∥Proceedings of the 10th International Conference on Mobile Systems,Application,and Services.New York:ACM,2012:197- 210.

[5]馬燕,袁蔚林,陳秀萬(wàn),等.基于WiFi和GPS組合定位算法的無(wú)縫定位方法研究 [J].地理與地理信息科學(xué),2013,29(3):6- 16.

MA Yan,YUAN Wei-lin,CHEN Xiu-wan,et al.A seamless positioning method research based on wireless local area network (WiFi) and GPS [J].Geography and Geo-Information Science,2013,29(3):6- 16.

[6]王小平,羅軍,沈昌祥.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)定位理論和算法 [J].計(jì)算機(jī)研究與發(fā)展,2011,48(3):353- 363.

WANG Xiao-ping,LUO Jun,SHEN Chang-xiang.Theory and algorithms on localization in wireless sensor networks [J].Journal of Computer Research and Development,2011,48(3):353- 363.

[7]WEI W,VIKRAM S,BANG W,et al.Coverage for target localization in wireless sensor networks [J].IEEE Tran-sactions on Wireless Communication,2008,7(2):667- 676.

[8]GAVSHIN Y,KRUUSMAA M.Improving area coverage by reversible object pushing [C]∥Proceedings of 15th International Conference on Advanced Robotices.Tallinn:IEEE, 2011:415- 420.

[9]JIANG X,FAN Y B,WEI S,et al.An algorithm of weighted Monte Carlo localization based on smallest enclosing circle [C]∥Proceedings of 2011 International Confe-rence on and 4th International Conference on Cyber,Phy-sical and Social Computing.Dalian:IEEE, 2011:157- 161.[10]陳華.確定任意形狀物體最小包圍盒的一種方法 [J].工程圖學(xué)學(xué)報(bào),2010,31(3):353- 363.

CHEN Hua.A method to generate the minimum bounding boxes for shape-arbitrary objects [J].Journal of Engineering Graphics,2010,31(3):353- 363.

[11]ULLRICH T,FUNFZIG C,FELLNER D W.Two diffe-rent views on collision detection [J].IEEE Potentials,2007,26(1):26- 30.

[12]LI G B,TANG J.A new K-NN query algorithm based on the clustering and sorting of minimum bounding rectangle [C]∥ Proceedings of 2nd International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC).Nanjing:IEEE,2010:196- 199.

[13]周培德.計(jì)算幾何：算法設(shè)計(jì)與分析 [M].3版.北京:清華大學(xué)出版社,2008:214- 216.

責(zé)任編輯：牛曉光

收稿日期:2015- 01- 14

*基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61370088)；國(guó)家國(guó)際科技合作專(zhuān)項(xiàng)項(xiàng)目(2014DFB10060);安徽省自然科學(xué)基金資助項(xiàng)目(1408085MKL80)

Foundation items: Supported by the National Natural Science Foundation of China(61370088),the International S & T Cooperation Program of China(2014DFB10060)and the Natural Science Foundation of Anhui Province(1408085MKL80)

作者簡(jiǎn)介:衛(wèi)星(1980-)，男，副教授，主要從事物聯(lián)網(wǎng)工程、離散事件動(dòng)態(tài)系統(tǒng)研究.E-mail:weixing72510@163.com

文章編號(hào):1000- 565X(2016)05- 0144- 07

中圖分類(lèi)號(hào)：TP 393.0

doi：10.3969/j.issn.1000-565X.2016.05.022

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

WEIXingHANJiang-hong

(School of Computer and Information∥Engineering Research Center of Safety Critical Industrial Measurement and Control Technology of the Ministry of Education, Hefei University of Technology, Hefei 230009, Anhui, China)

Abstract: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 max-min 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.

Key words:wireless localization; smallest enclosing rectangle; cover circle; convex planning