一種基于人工魚群算法的K覆蓋WiFi熱點安置方案

李鐘翔， 陳 蕾

（華東師范大學(xué)計算機科學(xué)與技術(shù)系，上海 200241）

一種基于人工魚群算法的K覆蓋WiFi熱點安置方案

李鐘翔， 陳 蕾

（華東師范大學(xué)計算機科學(xué)與技術(shù)系，上海 200241）

針對室內(nèi)定位導(dǎo)航、多路由選擇等熱門應(yīng)用中對多次無線信號覆蓋的需求，提出了一種基于改進的人工魚群優(yōu)化算法的K覆蓋安置策略.其中特別設(shè)計出一種簡單的障礙物干擾描述模型，以期更真實地刻畫應(yīng)用場景.仿真結(jié)果表明，我們的方法可在保證覆蓋的前提下，明顯節(jié)省A P數(shù)量同時改善節(jié)點的聚集.

K覆蓋； 人工魚群； WiFi

0 引 言

隨著無線通信技術(shù)的進步和推廣，通過無線信號進行定位已經(jīng)成為重要的熱門應(yīng)用.全球定位系統(tǒng)（G PS）能夠在戶外提供較準確的實時定位方案，但某些特殊環(huán)境（如車庫、商場、寫字樓）中，其信號覆蓋和定位精度卻很難滿足用戶需求.室內(nèi)定位有其特殊性：精度要求通常較高，墻壁等障礙物對信號強度影響較大；此外車庫、電梯等環(huán)境無法使用衛(wèi)星信號和蜂窩信號.在室內(nèi)場景下，基于WiFi技術(shù)的定位方案，逐漸引起人們的重視.為實現(xiàn)無線定位，研究者們提出了不同算法.這些算法無一不以無線信號的足夠覆蓋為前提，因此確保無線覆蓋就成為了定位系統(tǒng)中關(guān)鍵的一環(huán).此外，覆蓋問題還可以被應(yīng)用到如多路徑的路由選擇等問題中去.一個高效的覆蓋方案，不僅為我們提供較好的信號傳輸質(zhì)量，還能在一定程度上節(jié)省資源降低，系統(tǒng)成本.在無線覆蓋問題中，最基本的要求被稱為“一次覆蓋”，即對于所涉范圍的任意位置，都要求至少有一個A P裝置能夠?qū)ζ溥M行覆蓋以保證通信，我們注意到一些固定的設(shè)計模式被用于解決覆蓋問題［1］.然而由于實際應(yīng)用中覆蓋區(qū)域不規(guī)則，以及因為信號強度不穩(wěn)定造成的單節(jié)點覆蓋范圍不穩(wěn)定等原因，給這類設(shè)計思路帶來了挑戰(zhàn).隨機部署節(jié)點后通過移動節(jié)點達到優(yōu)化區(qū)域覆蓋成為不少學(xué)者關(guān)注的重點.在隨機部署節(jié)點的前提下，對于如何移動節(jié)點以高效地實現(xiàn)一次覆蓋，前人提出了不少算法，如Virtual Forces（V F）算法［2-3］，這是一種模仿力之間的相互作用來實現(xiàn)較好覆蓋的方案.遺傳算法、群智能優(yōu)化算法等也被廣泛用于對這個問題的研究和討論［4-7］.本文的算法設(shè)計在此前提下基于群智能算法中的魚群算法.

在很多情況下，一次覆蓋并不能滿足用戶的全部需求.例如幾類有代表性的定位算法：N N、K N N、三點定位法，都是以區(qū)域內(nèi)任何一位置獲取多個A P裝置的信號強度和位置信息為前提，這就需要實現(xiàn)多次覆蓋，即K覆蓋.在K覆蓋的要求下，前人提出了一些理想狀態(tài)下的全覆蓋的算法和一些設(shè)計模式.Jung-Eun Kim等人提出了一種在理想狀態(tài)下2次和3次覆蓋的高度優(yōu)化算法，實現(xiàn)了區(qū)域內(nèi)的全覆蓋［9］，但這類算法要求在無障礙物干擾的場景下實施，且無法推廣解決更高次數(shù)的覆蓋問題.L A A C A D算法在場景受限的情況下，針對無線傳感網(wǎng)設(shè)計的一種K覆蓋算法，即通過執(zhí)行K次一次覆蓋疊加，從而實現(xiàn)K覆蓋［9］；該算法會產(chǎn)生傳感器節(jié)點的聚集.而H e等人提出，A P點的聚集通常會使相鄰A P節(jié)點所提供的位置特征信息近似，造成資源的浪費；而且由于A P節(jié)點的信號波動，A P節(jié)點的聚集可能導(dǎo)致對待定位點位置的錯誤判斷［6］.故而A P節(jié)點的分布應(yīng)當(dāng)盡可能均勻.

對于如何解決障礙物對覆蓋造成的影響，Chang等人提出將區(qū)域圍繞障礙物將空間分成幾塊區(qū)域分別進行覆蓋［11］.W u等人提出在障礙物周圍按適當(dāng)距離圍成一圈以解決覆蓋［12］.這些算法選擇忽略節(jié)點信號穿越障礙物后依然能覆蓋到的部分來避免對障礙物帶來的信號衰減進行量化.

針對上述問題，本文的工作主要圍繞以下兩方面展開：①對基本的人工魚群算法進行了相應(yīng)改進，同時加入一些啟發(fā)式算法來實現(xiàn)有障礙物情況下的K覆蓋.在保證覆蓋的前提下盡可能節(jié)省A P節(jié)點的數(shù)量，并改善A P節(jié)點分布的聚集狀況；②提出了一種簡單易用的估計模型，對障礙物帶來的影響進行了量化.

1 相關(guān)的說明

1.1 人工魚群算法

人工魚群算法是群智能優(yōu)化算法中的一種，通過設(shè)計單個人工魚實體的感知和行動機制來與環(huán)境交互，以解決優(yōu)化問題，尋求近似最優(yōu)解.人工魚群算法的應(yīng)用范圍很廣，W ang等人將其用于區(qū)域的一次覆蓋，取得了不錯效果［8］.

人工魚群由大量人工魚組成.人工魚是一種真實魚的虛擬實體，它一般包括以下幾個基本屬性：人工魚的當(dāng)前狀態(tài)X，人工魚的視距dvisual，人工魚的步長dstep.針對覆蓋問題，本文假設(shè)每個人工魚代表一個A P節(jié)點，并根據(jù)A P節(jié)點的特性加入了人工魚探測距離屬性dcover，用于描述A P節(jié)點信號強度的覆蓋范圍.人工魚的狀態(tài)為其所在位置信息X（x，y）.得到人工魚模型如圖1所示：以dvisual為半徑的圓描述了人工魚的視野，描述覓食行為中，搜索食物的范圍；以dcover為半徑的圓描述了人工魚的信號的覆蓋面積；以dstep為半徑的圓描述了人工魚一次移動的范圍.

對于某一條人工魚，其所在的環(huán)境是指問題的解空間和其他人工魚的狀態(tài).人工魚對其所處的環(huán)境作出反應(yīng)，進而改變環(huán)境，影響其他人工魚.它對于環(huán)境的反應(yīng)方式主要依靠以下幾種基本行為：覓食、聚群、追尾、隨機.在覆蓋問題中，聚群行為的作用并不明顯，故而在本模型中，我們將聚群行為并入到追尾行為.

1.1.1 覓食行為

記區(qū)域內(nèi)某一點的食物量為Y，某一條人工魚i在由dvisual構(gòu)成的圓中搜尋狀態(tài)優(yōu)于自身所在點的位置food，并以dstep為界向其運動.對于food所在位置的查找可表示為

如果備選點的食物量Yfood＞Yi，則向其移動：

若備選點的食物量Yfood≤Yi，則執(zhí)行隨機行為.

1.1.2 追尾行為

在人工魚群算法中，某一人工魚與其他人工魚不應(yīng)相隔過遠，以防止遠離最優(yōu)解；同時也不宜過于接近，以防止聚集在局部最優(yōu)解處，而無法找到全局最優(yōu)解.在覆蓋問題中，相鄰兩個A P節(jié)點之間同樣要保持合適的距離.如圖2所示，對于一次覆蓋問題，理想狀態(tài)下兩條魚之間的距離為，此時場景內(nèi)不存在3次覆蓋的區(qū)域，是全覆蓋情況下的最優(yōu)解［3］.

現(xiàn)實場景中，由于地形和障礙物的影響無法達到上述理想情況.本模型的追尾行為，即是保持某一條人工魚與相鄰人工魚之間的距離，以保證重復(fù)覆蓋區(qū)域盡可能小的過程.

綜上，人工魚i對另一條人工魚j進行追尾行為是

1.1.3 隨機行為

該行為用于作為覓食行為和追尾行為的補充.即在沒有找到更優(yōu)良的食物點也不需要進行追尾行為時，人工魚將選擇一個隨機的方向游動.隨機行為看似隨機，其實增加了它尋覓其他人工魚和食物的范圍.

對于人工魚i有

1.2 覆蓋率

本文假設(shè)信號感知模型是概率感知的：某一點A（xA，yA）和某條人工魚Xi（xi，yi）間的距離為d，有A點被某條人工魚Xi覆蓋的概率為

其中Rp用于描述信號強度的不穩(wěn)定造成的A P節(jié)點覆蓋范圍的波動系數(shù)，?用于表述覆蓋對距離的敏感度.當(dāng)距離d＞（dcover-Rp）時，Xi對A點覆蓋的概率為Pi，以描述信號不穩(wěn)定帶來的覆蓋區(qū)域變化.A被覆蓋的概率P為

本文將需要覆蓋的區(qū)域用多個很小的網(wǎng)格進行劃分.若一個網(wǎng)格的4個頂點都被同一個A P節(jié)點覆蓋則認為該網(wǎng)格被覆蓋.計算某一個頂點A被覆蓋的概率P.設(shè)定一個閾值Pth，當(dāng)P＞Pth時，認為A點被覆蓋.記覆蓋的網(wǎng)格數(shù)為c1，總網(wǎng)格數(shù)為c，保證覆蓋率在f以上，即

2 K覆蓋算法

2.1 改進的人工魚群算法

本文先用少量的A P節(jié)點實現(xiàn)1次覆蓋，然后重復(fù)K次，以實現(xiàn)K覆蓋.在已覆蓋N次的情況下，進行第N+1次覆蓋（其中0≤N＜K）稱為一次邏輯覆蓋.

用人工魚群算法實現(xiàn)一次邏輯覆蓋時，本模型對基本的人工魚群加以改進，以適應(yīng)已存在N次覆蓋時的環(huán)境：

首先，之前的N次覆蓋中有一定區(qū)域達到了N+1次覆蓋甚至更高次的覆蓋，本模型對覓食行為進行修改，在找到的食物點A后先行判定其是否已達到N+1次覆蓋，如果達到則中止行為，只有A點被少于N+1個A P節(jié)點覆蓋，才進行原本的覓食行為.即在公式（1）找到食物點之后，除了判斷是否滿足條件Yfood＞Yi，還應(yīng)該判斷食物點覆蓋層數(shù)是否小于N+1.只有滿足這兩個條件才執(zhí)行公式（2）.

其次，要與前N次已安置好的A P節(jié)點保持一定距離以防止多個A P點聚集在某一個較小范圍.本模型要求新加入A P點在盡可能遠離前N次覆蓋布置的A P點的前提下，與本層的A P點實施追尾行為，這樣的過程稱為“規(guī)避行為”.當(dāng)然，隨著迭代次數(shù)的增加，A P節(jié)點也將越來越密集，新安置A P點與前N次布置的A P點間的距離可能與N有關(guān)，故將這個距離定為.得到公式如下：若人工魚i到前N次覆蓋產(chǎn)生的人工魚j之間的距離小于則有

迭代終止條件為第N+1次覆蓋率達到V1，則判定完成了第N+1次覆蓋.

此外，部分區(qū)域由于A P節(jié)點覆蓋范圍的重合，其覆蓋次數(shù)也會高于N次.且隨著覆蓋次數(shù)N的增加，我們發(fā)現(xiàn)在進行第N次A P節(jié)點的布置之后，覆蓋達到N+1次的區(qū)域也在逐漸增大，這時對人工魚群的初始狀態(tài)進行一些條件限制能夠加快算法收斂.圖3是進行了5次覆蓋之后各點被覆蓋的次數(shù)情況：白色區(qū)域被覆蓋次數(shù)小于6次，是執(zhí)行第6次覆蓋時需要覆蓋的區(qū)域；黑色區(qū)域被覆蓋次數(shù)大于或等于6次，應(yīng)當(dāng)盡量避免再去覆蓋以節(jié)省資源.從圖中可以發(fā)現(xiàn)，白色區(qū)域分布比較分散，且大部分臨近區(qū)域能被一個A P覆蓋.因此在這種情況下，尋找當(dāng)前情況下可覆蓋白色區(qū)域面積最大的一個點作為人工魚初始化的位置.在接下來的規(guī)避行為中，由于初始化階段本模型選擇的初始點已經(jīng)是當(dāng)前最優(yōu)，故不再進行覓食行為.對大多數(shù)較靠近的白色區(qū)域，都可以通過一條人工魚進行覆蓋，所以同一層中，魚與魚之間的吸引和排斥關(guān)系都不再重要，故不再執(zhí)行追尾行為，只執(zhí)行規(guī)避行為.當(dāng)?shù)贜次覆蓋以后達到N+1次覆蓋率為V2時，本模型采用上述方案實現(xiàn)第N+1次覆蓋.

綜上所述，有設(shè)計流程如圖4所示.

在取得場景中某一點與某一人工魚間的信號距離后，將其代入公式（5），來判斷該點是否被該人工魚覆蓋.

3 實驗仿真與實測用例

3.1 實驗仿真

本次實驗的仿真環(huán)境為Matlab7.1，計算機處理器是Intel（R）Core（T M）2 Duo C P U E P4400 2.00 G H z.取100×100大小，有一個障礙物的空間進行仿真.在程序的開始階段每實現(xiàn)一次邏輯覆蓋時，都將對30個人工魚進行隨機狀態(tài)的初始化來進行計算.當(dāng)層數(shù)增加到一定數(shù)量時，采用指定區(qū)域的方式初始化人工魚的位置，即覆蓋率已經(jīng)超過閾值V2時，點數(shù)不固定，根據(jù)實際仿真的情況來看，每次增加的人工魚將少于30個.我們使用的設(shè)置參數(shù)表如表1所示.（仿真中計drisual、dcover、dstep、Rp、r1、r2變量單位為1單位長）

本次仿真，記V1為99%作為接近100%迭代終止的閾值，該閾值可以根據(jù)實際應(yīng)用的需求進行調(diào)整，文獻3、文獻5和文獻8也采用了類似的方法［3，6，8］.對3次、5次、7次、8次、9次覆蓋分別進行3次仿真實驗之后取中間值，要使覆蓋率超過99%至少需要的點數(shù)如表2所示.

以5次覆蓋為例得到的效果圖如圖6所示，其中·代表的是障礙物.

圖7顯示了由基本魚群算法實現(xiàn)5次覆蓋的A P節(jié)點位置分布，圖8示意了由本文中提出的改進算法得到的布局情況.

對比圖7、圖8，可以看出改進后的人工魚群算法有相對均勻的部署結(jié)果，對A P點分布有顯著的優(yōu)化.

另外，優(yōu)化后K次覆蓋率達到99%使用的A P節(jié)點數(shù)也少于基本魚群算法.兩者的對比圖如圖9所示.

3.2 實測用例

針對一個小型地下車庫場景進行了實驗，過程是先用模擬手段進行安置規(guī)劃，再通過實際設(shè)備測試進行驗證.仿真實驗使用了7個A P節(jié)點對區(qū)域?qū)崿F(xiàn)了3次覆蓋.主要參數(shù)如表3所示.場景中的節(jié)點安置方案如圖10所示.

選取的A P節(jié)點為T P-LIN K的T L-M R10 U便攜式3 G路由器，-75db m閾值時該設(shè)備的覆蓋半徑約20 m.采用手機軟件WiFi分析儀進行信號強度測試.

實測結(jié)果顯示：可以保證區(qū)域內(nèi)位置有3個以上的A P節(jié)點的信號強度高于-75db m［13］，即在上述場景下，實測結(jié)果與仿真結(jié)果吻合，用例說明在上述場景下算法是正確的.

4 結(jié) 語

本文就如何實現(xiàn)高效的K覆蓋對基于人工魚群算法的改進和補充，建立了一個改進的K次覆蓋人工魚群算法的模型.保證了覆蓋區(qū)域內(nèi)99%的K覆蓋率，降低了使用A P點的個數(shù)，同時也較好的解決了多層情況下A P點聚集的問題.仿真結(jié)果表明隨著覆蓋層數(shù)的增加，改進算法帶來的節(jié)省A P節(jié)點的優(yōu)勢也越明顯.

本文設(shè)計一種障礙物對A P節(jié)點覆蓋范圍影響的模型.該障礙物模型的設(shè)計還比較簡單.實際應(yīng)用中，可以通過獲取大量的實測數(shù)據(jù)，并對其進行多項式擬合，以取得更好的效果.

［1］ BAI X，XUAN D，YUN Z，et al.Complete optimal deployment patterns for full-coverage and k-connectivity（k≤6）wireless sensor networks［C］//Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing.A C M，2008：401-410.

［2］ ZOU Y，CHAKRABARTY K.Sensor deployment and target localization based on virtual forces［C］//IN F O C O M 2003.Twenty-Second Annual Joint Conference of the IE E E Computer and Communications.IE E E Societies. IE E E，2003，2：1293-1303

［3］ YU X，HUANG W，LAN J，et al.A novel virtual force approach for node deployment in wireless sensor network［C］//Distributed Computing in Sensor Systems（D C O SS），2012 IE E E 8th International Conference on.IE E E，2012：359-363.

［4］ REDA S M，ABDELHAMID M，LATIFA O，et al.Efficient uncertainty-aware deployment algorithms for wireless sensor networks［C］//Wireless Communications and Networking Conference（W C N C），2012 IE E E.IE E E，2012：2163-2167.

［5］ NAVARRO M，DAVIS T W，LIANG Y，et al.A S W P：a long-term W S N deployment for environ mental monitoring［C］//Proceedings of the 12th international conference on Information processing in sensor networks.A C M，2013：351-352.

［6］ HE Y，MENG W X，MA L，et al.Rapid deployment of APs in W L A N indoor positioning system［C］//Proceedings of the 2011 6th International ICS T Conference on Communications and Networking in China.IE E E Computer Society，2011：268-273.

［7］ WANG G，GUO L，DUAN H，et al.Dynamic deployment of wireless sensor networks by biogeography based optimization algorithm［J］.Journal of Sensor and Actuator Networks，2012，1（2）：86-96.

［8］ WANG Y Y，LIAO H M，H U H Y.Wireless sensor network deployment using an optimized artificial fish swarm algorithm［C］//Computer Science and Electronics Engineering（ICCSEE），2012 International Conference on. IE E E，2012，2：90-94.

［9］ KIM J E，HAN J，LEEC G.Optimal 3-coverage with minimum separation requirements for ubiquitous computing environments［J］.Mobile Networks and Applications，2009，14（5）：556-570.

［10］ LI F，LUO J，XIN S Q，et al.L A A C A D：Load balancing k-area coverage through autonomous deployment in wireless sensor networks［C］//Distributed Computing Systems（ICDCS），2012 IE E E 32nd International Conference on.IE E E，2012：566-575.

［11］ CHANG C Y，CHEN Y C，CHANG H R.Obstacle-resistant deployment algorithms for wireless sensor networks［J］.Vehicular Technology，IEEE Transactions on，2009，58（6）：2925-2941.

［12］ WU C H，LEE K C，CHUANG Y C.A Delaunay triangulation based method for wireless sensor network deployment［J］.Computer Communications，2007，30（14）：2744-2752.

［13］ PATRO A，GOVINDAN S，BANERJEE S.Observing ho me wireless experience through WiFi APs［C］//Proceedings of the 19th annual international conference on Mobile computing&networking.A C M，2013：339-350.

（責(zé)任編輯 李 藝）

K-coverage of WiFi signal node deployment based on AFSA

LI Zhong-xiang， C H E N Lei
（Department of Computer Science and Technology，East China Normal University，Shanghai 200241，China）

O n the requirement of multiple wireless coverage in so me hot applications like indoor positioning and navigation，multipath routing etc.，this paper presented aK-coverage placement scheme based on an improved Artificial Fish-S warm Algorithm（A FS A）.A simple obstacle interference describing model was also designed to make our simulation scenario closer to a real one.The simulative results showed that our method could obviously reduce the number of signal nodes and their aggregation on the premise of coverage.

K-coverage； A FS A； WiFi

T P393.17

A D OI：10.3969/j.issn.1000-5641.2015.01.019

1000-5641（2015）01-0151-10

2014-05

李鐘翔，男，碩士研究生，研究方向為計算機網(wǎng)絡(luò).E-mail：51131201054@ecnu.cn.

陳蕾，女，副教授，研究生導(dǎo)師，研究方向為計算機網(wǎng)絡(luò).E-mail：lchen@cs.ecnu.edu.cn.