WMSNs中基于改進(jìn)QGA的覆蓋增強(qiáng)算法*

王延菲，馮秀芳，朱曉軍

(太原理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西太原030024)

0 引言

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

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

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

1 傳感器覆蓋模型建立

1.1 模型建立約束

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

2)部署后，節(jié)點(diǎn)可移動(dòng)改變當(dāng)前位置和繞自身的坐標(biāo)調(diào)節(jié)主感知方向;

3)假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)均了解自身信息，鄰居節(jié)點(diǎn)間可進(jìn)行可靠通信。

1.2 有向感知模型

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

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

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

假設(shè)監(jiān)測(cè)區(qū)域中存在點(diǎn)Z，若滿足式(1)，說(shuō)明點(diǎn)Z被網(wǎng)絡(luò)中的節(jié)點(diǎn)所覆蓋，式(1)的定義如下

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

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

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

2.1 QGA

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

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

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

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

3)評(píng)估u(t0)中個(gè)體的適應(yīng)值，記錄最優(yōu)個(gè)體，并將其作為下一次演化的目標(biāo)值;

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

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

評(píng)估p(t)的適應(yīng)度值;

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

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

2.2 QGA的不足

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

3 改進(jìn)算法實(shí)現(xiàn)

針對(duì)QGA存在的問(wèn)題，對(duì)算法進(jìn)行改進(jìn):1)通過(guò)適應(yīng)度值選出多條最優(yōu)染色體組來(lái)引導(dǎo)種群迭代，增加種群多樣性;2)采用自適應(yīng)機(jī)制調(diào)整旋轉(zhuǎn)角，增強(qiáng)算法的收斂速度和搜索能力;3)采用新的量子變異方法，提高搜索結(jié)果向最優(yōu)解貼近的速度。

3.1 編碼

編碼過(guò)程如圖2所示。

圖2 編碼過(guò)程示意圖Fig 2 Schematic diagram of coding process

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

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

3.2 適應(yīng)度函數(shù)定義

適應(yīng)度函數(shù)是挑選染色體的重要評(píng)估標(biāo)準(zhǔn)，本文使用覆蓋率函數(shù)作為適應(yīng)度函數(shù)，記作fg，其定義如下

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

3.3 量子比特操作

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

其中，θ為旋轉(zhuǎn)角，［α，β］T為未做改變前的量子比特，［α'，β'］T為經(jīng)過(guò)旋轉(zhuǎn)之后的量子比特。

在量子旋轉(zhuǎn)中，旋轉(zhuǎn)角的選擇對(duì)于算法尤為重要，它的幅度選擇會(huì)影響算法的收斂速度，若幅度過(guò)大，會(huì)使算法陷入早熟;反之，算法的收斂速度又會(huì)變慢。本文按式(6)對(duì)旋轉(zhuǎn)角度θ進(jìn)行自適應(yīng)調(diào)整

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

傳統(tǒng)的量子變異都是通過(guò)式(7)來(lái)實(shí)現(xiàn)的，即互換量子比特的概率幅值

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

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

3.4 生成子代，確定演化目標(biāo)

在演化目標(biāo)的選取上，改進(jìn)算法選擇適應(yīng)度最高的b條染色體構(gòu)成優(yōu)化目標(biāo)的待選組。通過(guò)實(shí)踐分析，b的取值可表示為

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

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

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

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

4 仿真試驗(yàn)

4.1 覆蓋效果

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

表1 算法參數(shù)取值Tab 1 Algorithm parameter values

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

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

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

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

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

4.2 算法效率

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

圖6 算法效率對(duì)比圖Fig 6 Comparison diagram of algorithm efficiency

圖7、圖8顯示了在不同的節(jié)點(diǎn)數(shù)、感知半徑的情況下，算法覆蓋率的提高百分比，可以看出:改進(jìn)的算法具有更好的表現(xiàn)。總之，相比QGA算法，從覆蓋效果、算法的收斂速度以及搜索能力等方面來(lái)看，本文提出的改進(jìn)的QGA對(duì)于傳感器網(wǎng)絡(luò)的覆蓋問(wèn)題具有良好的效率。

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

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

5 結(jié)論

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

［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ìn)的量子遺傳算法及其在測(cè)試數(shù)據(jù)生成中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用，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］曾 成，趙錫均.改進(jìn)量子遺傳算PID參數(shù)整定中應(yīng)用［J］.電力自動(dòng)化設(shè)備，2009，29(10):125-127.

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

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

［10］刑煥來(lái)，潘 煒，鄒喜華.一種解決組合優(yōu)化問(wèn)題的改進(jìn)型量子遺傳算法［J］.電子學(xué)報(bào)，2007，35(10):1999-2002.