WMSNs中基于改進QGA的覆蓋增強算法*

王延菲，馮秀芳，朱曉軍

(太原理工大學計算機科學與技術學院，山西太原030024)

0 引言

無線多媒體傳感器網絡(wireless multimedia sensor networks，WMSNs)是在傳統(tǒng)無線傳感器網絡(WSNs)的基礎上增加了多媒體技術的一個新型研究領域［1，2］，如今，WMSNs在環(huán)境監(jiān)控、軍事部署、遠程醫(yī)療、智能家居等領域都得到了廣泛的應用。但在傳感器網絡的實際部署過程中，存在監(jiān)控重疊區(qū)與盲區(qū)的情況，因此，需要一定的優(yōu)化手段來增加網絡的覆蓋率，提高整個網絡的服務質量。

Han K H等人提出了量子遺傳算法［3］(quantum genetic algorithm，QGA)，它是在遺傳算法(genetic algorithm，GA)基礎上發(fā)展起來的一種全局搜索算法。GA是一種隨機的搜索算法，具有全局搜索能力強，并行處理性好等優(yōu)點，但同時也存在收斂速度慢，易收斂于局部最優(yōu)的缺陷，QGA在GA的基礎上對算法的多方面進行了改進，相對加快了算法的收斂速度，但易陷入局部最優(yōu)解的問題依然存在。

本文對WMSNs中的覆蓋問題進行研究，將覆蓋看做一種類優(yōu)化問題并采用改進的QGA算法進行求解，該算法在QGA的基礎上采用多條染色體組來共同指導迭代，同時在量子旋轉階段采用自適應調整旋轉角方式，使用新的量子變異方法，基于節(jié)點的有向感知模型，對傳感器的位置和感知方向進行調整，使得監(jiān)測區(qū)域擁有更好的覆蓋效果。

1 傳感器覆蓋模型建立

1.1 模型建立約束

l)網絡由n個相同的視頻傳感器節(jié)點構成，節(jié)點的主感知方向在［0，2π］上均勻分布;

2)部署后，節(jié)點可移動改變當前位置和繞自身的坐標調節(jié)主感知方向;

3)假設網絡中的節(jié)點均了解自身信息，鄰居節(jié)點間可進行可靠通信。

1.2 有向感知模型

本文采用有向感知模型，模型如圖1所示。

圖1 有向感知模型Fig 1 Directional sensing model

該模型由四元組(P，R，ω，→v)表示，其中，P為節(jié)點的當前位置，R為感知半徑，2ω為視角范圍，→v為單位向量，即主感知方向［4］。

假設監(jiān)測區(qū)域中存在點Z，若滿足式(1)，說明點Z被網絡中的節(jié)點所覆蓋，式(1)的定義如下

在傳感器網絡中任意選擇節(jié)點i，1≤i≤n，其坐標為(xi，yi)，主感知方向記作vi，可覆蓋的目標點集合記作gi，經算法調整后，節(jié)點的坐標變?yōu)?x'i，y'i)，主感知方向為v'i，此時可覆蓋的目標點集合為g'i，設監(jiān)測區(qū)域由G個點組成，節(jié)點調整前、后監(jiān)測區(qū)域的覆蓋率、區(qū)域覆蓋率的變化分別記作 H，H'，ΔH，ΔH 的定義如式(2)

覆蓋的目的就是使得網絡的覆蓋率較調整前有較大改變，即ΔH達到最大，因此，監(jiān)測區(qū)域的覆蓋優(yōu)化就轉化成為了ΔH的最大值求解問題，在分析式(2)后發(fā)現均為常量，ΔH最大值求解就等價于求，影響的因素有(x'i，y'i)，v'i。因此，本文的主要任務就是使用改進的QGA求得)相對應一組的解向量。

2 基本優(yōu)化算法

2.1 QGA

QGA是在GA的基礎上演化的一種基于量子計算的概率優(yōu)化方法，算法用量子比特的概率幅編碼染色體，采用量子旋轉門實現染色體更新，完成目標優(yōu)化。很多文獻實踐證明，QGA擁有收斂速度快、種群多樣且規(guī)模小、尋優(yōu)能力強等［5］優(yōu)點，在效率上明顯優(yōu)于遺傳算法。

QGA 的基本步驟［6，7］如下:

1)生成初始種群G(t0);

2)測量G(t0)的個體，得到初始狀態(tài)u(t0);

3)評估u(t0)中個體的適應值，記錄最優(yōu)個體，并將其作為下一次演化的目標值;

4)while非結束條件do。begin:

對種群G(t)測量，得到狀態(tài)記作p(t);

評估p(t)的適應度值;

通過量子旋轉門、量子非門更新種群，得到下一代種群，記作G(t+1);

記錄最佳個體狀態(tài)、適應度值。End

2.2 QGA的不足

相較于簡單GA，QGA擁有較快的收斂速度，但依然存在易陷入局部最優(yōu)和全局搜索能力欠佳的缺點［8］，主要是因為:1)QGA通過選出當前的最優(yōu)解來引導子代演化，這樣的演化過程方向過于單一，易使求解過程陷入局部最優(yōu);2)量子旋轉角是影響搜索的收斂速度和效率的主要因素之一，在QGA中旋轉角的取值相對固定，無法靈活地指導染色體的變異方向;3)QGA的量子變異過程較為簡單隨意，會一定程度地影響算法的收斂速度。本文將針對以上三點對QGA進行改進。

3 改進算法實現

針對QGA存在的問題，對算法進行改進:1)通過適應度值選出多條最優(yōu)染色體組來引導種群迭代，增加種群多樣性;2)采用自適應機制調整旋轉角，增強算法的收斂速度和搜索能力;3)采用新的量子變異方法，提高搜索結果向最優(yōu)解貼近的速度。

3.1 編碼

編碼過程如圖2所示。

圖2 編碼過程示意圖Fig 2 Schematic diagram of coding process

1)染色體是由M個基因組成的，其中，第j個節(jié)點的位置信息由第j個基因表示(1≤j≤M)。

2)編碼［9］的表現形式為:qx+qy+qz，其中，qx為節(jié)點的橫坐標，qy為節(jié)點的縱坐標，qz為節(jié)點的感知方向。

3.2 適應度函數定義

適應度函數是挑選染色體的重要評估標準，本文使用覆蓋率函數作為適應度函數，記作fg，其定義如下

為了簡化操作，這里離散監(jiān)測區(qū)域等距選擇T個點，節(jié)點可覆蓋的點有Tg個，則定義f'g如式(2)來近似表示fs

3.3 量子比特操作

量子比特有2種操作，分別為量子旋轉、量子變異［10］。量子旋轉的操作如式(5)所示

其中，θ為旋轉角，［α，β］T為未做改變前的量子比特，［α'，β'］T為經過旋轉之后的量子比特。

在量子旋轉中，旋轉角的選擇對于算法尤為重要，它的幅度選擇會影響算法的收斂速度，若幅度過大，會使算法陷入早熟;反之，算法的收斂速度又會變慢。本文按式(6)對旋轉角度θ進行自適應調整

其中，p1，p2∈(0.001π，0.05π)，fmax是種群中進化的目標值，f為量子旋轉的個體的適應度值，favg為當代種群的平均適應度值，當適應度值小于平均值時，說明個體較差，此時使用相對大的旋轉角對它進行改變;反之，則表明個體較為優(yōu)秀，此時據其適應度對旋轉角進行較小的調整，這樣確保了種群的多樣性和算法收斂速度。

傳統(tǒng)的量子變異都是通過式(7)來實現的，即互換量子比特的概率幅值

但是，式(7)具有較大的隨機性，很容易使得個體向錯誤的解空間發(fā)展，導致收斂速度變慢。

針對此問題，本算法首先將染色體轉換為二進制串，從而根據變異概率改變其中的一位或多位，修改采用取反規(guī)則。設變異位為c，變異后為c'，轉換過程如式(8)所示

3.4 生成子代，確定演化目標

在演化目標的選取上，改進算法選擇適應度最高的b條染色體構成優(yōu)化目標的待選組。通過實踐分析，b的取值可表示為

其中，f為一選定增函數，M表示解空間，E表示局部最優(yōu)解個數，D(M)表示解空間的方差。

算法的每次迭代都會重新確定b條染色體的構成。設當前最優(yōu)的b條染色體的適應度值集合為Q={e1，e2，…，eb}，其父代的b條最優(yōu)染色體的適應度值集合為Q'={e'1，e'2，…，e'b}，按式(9)求得最優(yōu)的染色體集合 Qmax，其中，max為求最大值函數

將Qmax作為下一代的優(yōu)化目標待選組。

選擇演化目標時，并選出一條染色體 ek∈Qmax，k=random()，1≤random()≤b，其中，random()為隨機數生成函數，該方法保證了種群的多樣性。

4 仿真試驗

4.1 覆蓋效果

本文實驗部分采用Matlab 7.0為仿真環(huán)境，首先選擇80個有向傳感器節(jié)點部署在1 000 cm×1 000 cm的監(jiān)測區(qū)域，開始節(jié)點視角為60°，感知半徑為70 cm，實驗將對比采用簡單QGA和改進的QGA調整傳感器網絡部署的覆蓋效果，算法涉及的參數如表1所示。

表1 算法參數取值Tab 1 Algorithm parameter values

圖3為隨機部署80個節(jié)點的監(jiān)測區(qū)域分布圖，從中可以看出:部分區(qū)域的節(jié)點分布過于集中，出現了重疊區(qū)域，而有些區(qū)域則沒有被節(jié)點覆蓋，因此，整個檢測區(qū)域中不能實現最大化覆蓋。圖4為通過傳統(tǒng)QGA優(yōu)化監(jiān)測區(qū)域的覆蓋情況，圖5(a)，(b)分別為通過改進的QGA改善節(jié)點位置與感知方向的150次迭代和200次代迭代的覆蓋效果。

圖3 80個節(jié)點的初始部署Fig 3 Initial deployment of 80 nodes

從圖4可以看出:使用傳統(tǒng)的QGA迭代200次后可以使得監(jiān)測區(qū)域的節(jié)點分布較為均勻，但依然存在一些空白的監(jiān)測區(qū)域，而分析圖5(a)顯示的使用本文提出的改進的QGA在迭代150次的效果，結果具有比圖4更好的覆蓋效果，同時相比于圖5(a)，圖5(b)的結點分布更加均勻，盲區(qū)更少，說明改進的QGA算法在150次迭代之后還在搜索最優(yōu)，依然沒有陷入局部最優(yōu)，因此，可以看出改進的算法擁有優(yōu)化效果和全局搜索能力。

圖4 QGA的優(yōu)化覆蓋效果Fig 4 Optimization coverage effect of QGA

圖5 改進算法優(yōu)化150次和200次迭代的覆蓋效果Fig 5 Optimize coverage effect of improved algorithm

4.2 算法效率

圖6顯示了2種算法最優(yōu)解的進化過程，QGA算法在開始搜索時進化速度較快，但是50次迭代后搜索速度開始變緩，此時可以認為QGA算法陷入了局部最優(yōu)，無法再尋找更好的解。而改進的QGA算法在開始與QGA具有相差不大的搜索能力，然而，該算法在150次迭代時依然在更新，說明其全局搜索能力更強，算法使用目標染色體組來引導群體的迭代，使得算法不易提早收斂，同時采用自適應的旋轉角度和新的量子變異方法，可以看出:改進的算法在搜索過程覆蓋率變化的更快，達到最優(yōu)覆蓋率的時間更早，擁有更好的收斂速度。

圖6 算法效率對比圖Fig 6 Comparison diagram of algorithm efficiency

圖7、圖8顯示了在不同的節(jié)點數、感知半徑的情況下，算法覆蓋率的提高百分比，可以看出:改進的算法具有更好的表現?？傊啾萉GA算法，從覆蓋效果、算法的收斂速度以及搜索能力等方面來看，本文提出的改進的QGA對于傳感器網絡的覆蓋問題具有良好的效率。

圖7 不同節(jié)點數下的算法比較Fig 7 Algorithm comparison in different number of nodes

圖8 不同感知半徑下的算法比較Fig 8 Algorithm comparison in different perception radius

5 結論

本文使用改進的QGA來優(yōu)化WMSNs中節(jié)點的位置、感知方向，算法針對QGA易陷入局部最優(yōu)解的缺點，使用多條最優(yōu)染色體組成的優(yōu)化目標組來引導算法的迭代，增加種群的多樣性，同時采用自適應的量子旋轉角和新的量子變異方法來改善算法的收斂速度，從實驗的仿真結果可以看出:相比于QGA，改進的算法在覆蓋效果和執(zhí)行效率方面都有更好的表現。

［1］Kandris D，Tsagkaropouios M，Politis I，et al.Energy efficient and perceived QoSaware video routing over wireless multimedia sensor networks［J］.Ad Hoc Networks，2011，9(4):591-607.

［2］Akyldiz IF，Melodia T，Chowdhury K R.A survey on wireless multimedia sensor networks［J］.Computer Networks，2007，5(14):921-960.

［3］Han K H，Ki MJH.Genetic quantum algorithm and its application to combinatorial opti mization problem［C］∥Proc of the 2000 Congress on Evolutionary Computation，New York:IEEE，2000:1354-1360.

［4］Tao D，Ma H D，Liu L.A virtual potential field based coverageenhancing algorithm for directional sensor networks［J］.Journal of Software，2007，18(5):1152-1163.

［5］周 綺，蔣淑娟，趙雪峰.改進的量子遺傳算法及其在測試數據生成中的應用［J］.計算機應用，2012，32(2):557-560.

［6］Lee JC，Lin W M，Liao G C，et al.Quantum genetic algorithm for dynamic economic dispatch with valve-point effects and including wind power system［J］.International Journal of Electrical Power＆ Energy Systems，2011，33(2):189-197.

［7］曾 成，趙錫均.改進量子遺傳算PID參數整定中應用［J］.電力自動化設備，2009，29(10):125-127.

［8］朱筱蓉，張興華.基于改進量子遺傳算法的連續(xù)函數優(yōu)化研究［J］.計算機工程與設計，2007，28(21):5195-5197.

［9］周 殊，潘 煒，羅 斌，等.一種基于粒子群優(yōu)化方法的改進量子遺傳算法及應用［J］.電子學報，2006，34(5):897-901.

［10］刑煥來，潘 煒，鄒喜華.一種解決組合優(yōu)化問題的改進型量子遺傳算法［J］.電子學報，2007，35(10):1999-2002.