基于改進離散粒子群的蜂窩網(wǎng)絡(luò)信道分配

馮志強，賈振紅，許國軍

（1.新疆大學(xué) 信息科學(xué)與工程學(xué)院，新疆 烏魯木齊830046；2.中國移動通信集團新疆有限公司，新疆烏魯木齊830063）

0 引 言

在蜂窩移動通信網(wǎng)絡(luò)中，隨著用戶的急劇增長，可用的頻率資源變得極為稀少，為了提高頻譜的利用率必須要引入較優(yōu)的頻率分配策略。頻率分配，又稱為信道分配問題 （channel assignment problem），屬于組合優(yōu)化中的 NP（nondeterministic polynomial）完備問題。針對信道分配問題國內(nèi)外提出的優(yōu)化算法有：蟻群算法、神經(jīng)網(wǎng)絡(luò)算法、模擬退火算法、遺傳算法和進化策略等［1－7］，這些優(yōu)化算法已經(jīng)被證明可以用來解決信道分配問題，但這些算法在搜索最優(yōu)解的過程中，依然存在算法復(fù)雜、收斂率較低、容易陷入局部最優(yōu)解等缺點。粒子群算法是新興的群智能算法，參數(shù)簡單和收斂迅速使其得到了廣泛的關(guān)注和應(yīng)用。粒子群算法極易早熟，如何增加算法的全局搜索能力，已經(jīng)成為研究的熱點。針對上述問題，本文提出了一種改進的離散粒子群優(yōu)化算法 （IDPSO）。該算法根據(jù)文化算法的思想設(shè)計了最優(yōu)漸進式變異算子，使一個最優(yōu)粒子向著全局最優(yōu)解變異，其它最優(yōu)粒子進行隨機變異，增加了粒子的多樣性，提高了算法的收斂率。又因采用了最小間距編碼，壓縮了求解空間，使得算法的收斂速度得到提高。

1 信道分配問題模型

在蜂窩小區(qū)制中，CAP要考慮的電磁兼容 （EMC）限制有：①同信道約束 （CCC）；②鄰信道約束 （ACC）；③同小區(qū)約束 （CSC）［8］。數(shù)學(xué)上建立的信道分配問題模型詳見文獻 ［8］，代價函數(shù)為

其中F是一個n×m的矩陣，表示一種信道分配方案，若f（i，a）＝1，表示信道a分配給小區(qū)i，若f （i，a）＝0，表示信道a未分配給任何小區(qū)。當(dāng)所有的限制都滿足時，代價函數(shù)C（F）＝0，表示找到了一種最優(yōu)的分配方案。CAP問題的目的就是找到一個解F使得C （P）＝0。

2 離散粒子群算法

粒子群優(yōu)化算法是一種新興的智能優(yōu)化算法，算法結(jié)構(gòu)簡單，求解速度快。離散粒子群算法在粒子群算法的基礎(chǔ)上被提出，用來解決工程中的離散問題。離散粒子群算法根據(jù)如下公式更新粒子的速度和位置［9］

其中c1、c2和c3是取值在0到1之間的常數(shù)，vi（t）表示t時刻粒子i的速度，xi（t）表示t時刻粒子i的位置，pi（t）表示t時刻粒子i的局部最優(yōu)位置，pg（t）表示t時刻粒子i的全局最優(yōu)位置。

3 改進的離散粒子群算法

3.1 個體編碼

本文采用了文獻 ［10］的最小間距編碼方案，編碼前的二進制串長度n，編碼后二進制串的長度是：n－ （d－1）（dmin－1）。n表示可用的信道數(shù)，d表示小區(qū)的信道需求，dmin表示同小區(qū)的最小信道間隔。對于固定的信道數(shù)，小區(qū)需求d越大，編碼后的長度越小，解空間的壓縮比越大。編碼后的粒子滿足CSC約束條件，代價函數(shù)可以簡化為［10］

在工程實際應(yīng)用中，在滿足用戶需求的情況下，必須使已用頻點數(shù)越小越好。為了求得最小頻點數(shù)，采用如下代價函數(shù)

其中α和 （是取值介于0和1之間的系數(shù)，M表示當(dāng)前分配方案中所需的頻點數(shù)。當(dāng)O （F）求得最小值時，C （F）和M也必然求得最小值。

3.2 粒子的位置和速度

粒子的位置P表示為分配給一個小區(qū)的頻率組成的m維向量，m表示小區(qū)的頻率需求。P的第i維表示小區(qū)的第i個需求所分配的頻率號，其公式表示如下

其中ci∈ ｛1，2，3，…，C｝，C表示最大的頻率數(shù)目，m表示小區(qū)的頻率需求。

本文使用交換算子 （i，j）表示小區(qū)的當(dāng)前信道i和即將要切換到的信道j，m個交換算子就構(gòu)成了粒子的速度

如果令V1＝ （i1，i2，i3，…，im），V2＝ （j1，j2，j3，…，jm），V1就是粒子的當(dāng)前位置，V2就是粒子要移動到的目的位置。粒子的位置減法運算公式［9］變?yōu)椋篤＝V1ΘV2，V1＝P1，V2＝P2。因此，可以由粒子位置P1和P2直接得到粒子的速度。P1和P2中可能存在相同的信道，直接由P1和P2得到的速度交換算子，使粒子在移動后可能就不再滿足小區(qū)的信道需求了。因此，將得到的V2限定如下

這樣就由粒子位置P1和P2形成了粒子速度V，粒子按速度V移動后仍滿足小區(qū)的頻點需求。式 （3）和式 （4）中的其他運算規(guī)則詳見文獻 ［9］。

3.3 最優(yōu)漸進式變異算子

在粒子的位置更新過程中，隨著粒子向最優(yōu)粒子的靠攏，會出現(xiàn)多個最優(yōu)粒子，從而降低了粒子的多樣性，使算法陷入局部最優(yōu)解而無法獲得全局最優(yōu)解。為了提高算法的局部搜索能力，保證算法的收斂速度和收斂率，本文設(shè)計了最優(yōu)漸進式變異算子：①統(tǒng)計當(dāng)前粒子群中的最優(yōu)粒子個數(shù)，并從最優(yōu)粒子中隨機選擇一個做為全局最優(yōu)粒子。②對這個全局最優(yōu)粒子，將小區(qū)i的第n個已分配信道隨機替換為未分配的信道 （i表示小區(qū)號，n表示小區(qū)i中的第n個需求）。③計算已替換后粒子的適應(yīng)度，如果該適應(yīng)度優(yōu)于替換前粒子的適應(yīng)度，則用變異后的粒子替代之前的粒子，否則，恢復(fù)已變異的元素。④反復(fù)執(zhí)行②和③直到所有小區(qū)的所有信道需求元素都經(jīng)過替換。⑤當(dāng)所有的需求信道都替換后仍無較優(yōu)粒子出現(xiàn)，則保留這個最優(yōu)粒子，對剩下的最優(yōu)粒子進行隨機變異。這種變異方式使最優(yōu)粒子總是朝著問題的最優(yōu)解方向變異，防止了退化的出現(xiàn)，減少了最優(yōu)粒子的個數(shù)，提高了粒子的多樣性，使粒子跳出局部最優(yōu)值，增強了算法的全局搜索能力。最優(yōu)漸進式變異算子可以表示為

式中：F——最優(yōu)漸進式變異操作，fi——粒子i的適應(yīng)度，fb——最優(yōu)粒子的適應(yīng)度。粒子按式 （3）更新位置后，按式 （10）更新位置。最優(yōu)漸進式變異算子是以增加算法的運算時間來提高進化過程中的種群多樣性的，從而使算法的收斂率得到提高。

3.4 變異概率的確定

粒子位置的不同而表現(xiàn)出的多樣性稱為種群多樣性，它是評價粒子群搜索可能解的重要尺度［11］。當(dāng)粒子的多樣性降低時，粒子開始出現(xiàn)聚集現(xiàn)象。只有粒子出現(xiàn)聚集的時候才需要對粒子進行變異，而且每個粒子的變異概率應(yīng)該是不一樣的。本文引入文獻 ［11］中的方法來判斷粒子的聚集程度。定義

式中：fi——第i個粒子的適應(yīng)度，favg——全體粒子的平均適應(yīng)度。從式 （11）可以看出：α2反映了粒子的聚集程度，其值越小，說明粒子的聚集程度越高，可以將這個值作為變異發(fā)生的條件。當(dāng)α2＝0時算法要么陷入局部最優(yōu)，要么已經(jīng)找到全局最優(yōu)。

為了保證進化的平穩(wěn)性，在粒子沒有聚集或聚集較小的時候，應(yīng)以較小的概率對粒子進行變異甚至不變異，而粒子聚集比較嚴重時，應(yīng)該以較大的概率對粒子進行變異。因此，在迭代的過程中，變異概率應(yīng)該是動態(tài)變化的，不同粒子的變異概率也是不同的。本文修改正態(tài)分布函數(shù)為變異概率公式

當(dāng)個體適應(yīng)度接近平均適應(yīng)度時取得較大的變異概率，相反，變異概率會很小。變異概率在0和1之間，只有當(dāng)粒子聚集嚴重時才會以概率1進行變異。綜上，當(dāng)α2＜C時，按照式 （12）的變異概率執(zhí)行最優(yōu)漸進式變異算子。

3.5 算法復(fù)雜度分析

粒子群算法的時間復(fù)雜度主要依賴于迭代次數(shù)t、粒子維數(shù)m和粒子的適應(yīng)度計算，這里認為粒子數(shù)是一個常數(shù)。在本文中一個m×n的二維矩陣代表了一個粒子，則適應(yīng)度函數(shù)執(zhí)行一次的時間復(fù)雜度是O （m2×n），在求解的過程中的時間復(fù)雜度是O （m2×n×t）。本文引入了最優(yōu)漸進式變異算子，根據(jù)上文表述可知其時間復(fù)雜度是O （m2×n×p），其中p是最優(yōu)粒子的個數(shù)，在每次迭代中，最優(yōu)粒子數(shù)目都是在變化的，則在求解過程中的時間復(fù)雜度是O（m2×n×p×t）。綜上，本文算法的時間復(fù)雜度是O （m2×n×p×t）。

3.6 粒子位置初始化

實踐表明：根據(jù)先驗知識對粒子位置進行初始化，能夠生成適應(yīng)度較高的初始粒子群，能夠提高算法的收斂速度和收斂率。本文根據(jù)最大需求最小沖突的思想，對文獻［11］的初始化方法進行了簡化：對一個小區(qū)，在可用的頻率中找到一個不與其它小區(qū)沖突的頻率，從這個頻率開始按照頻率號遞增和遞減交替形成頻率分配表，再按照小區(qū)的需求進行分配。此方法可有效的提高初始種群的質(zhì)量，和其它初始化方法相比，此方法更易實現(xiàn)。

3.7 本文算法步驟

（1）設(shè)置算法的參數(shù)，設(shè)置粒子數(shù)目、最大迭代次數(shù)、以及c1，c2，c3的初始值，根據(jù)本文的方法初始化粒子的位置。

（2）根據(jù)式 （5）或式 （6）計算粒子的適應(yīng)度，更新粒子的局部最優(yōu)值和全局最優(yōu)值。

（3）根據(jù)式 （11）判斷當(dāng)前粒子是否出現(xiàn)聚集，若出現(xiàn)聚集按式 （12）的變異概率對最優(yōu)粒子執(zhí)行最優(yōu)漸進式變異；若未出現(xiàn)聚集執(zhí)行步驟 （4）。

（4）根據(jù)式 （3）形成粒子的新速度。

（5）根據(jù)式 （4）得到粒子的新位置。

（6）終止條件判斷，若已尋找到最優(yōu)個體或者達到最大迭代次數(shù)，則算法結(jié)束，否則執(zhí)行步驟 （2）。

4 仿 真

本文算法采用MATLAB語言編寫，21小區(qū)問題的兼容矩陣和需求向量見文獻 ［5］。本文先設(shè)置最大迭代次數(shù)為500，粒子個數(shù)為50，c1＝0.9，c2＝0.5，c2＝0.7，α＝0.6，β＝0.4，C＝25，粒子的適應(yīng)度評價函數(shù)是式 （6），進行迭代計算尋找到最小的可用頻點數(shù)。尋找到最小可用頻點數(shù)后，粒子的適應(yīng)度評價函數(shù)是式 （5），按照頻點數(shù)為80、70、52、51、45、42、40進行了100次實驗，其他參數(shù)不變。

圖1給出了以式 （6）為個體的適應(yīng)度評價函數(shù)的仿真圖，從圖中可見：當(dāng)?shù)M行到第11代時C（P）為0，即出現(xiàn)了滿足EMC需求的頻率分配方案，此時需要的頻點數(shù)為57。隨著迭代的繼續(xù)進行，系統(tǒng)所需的最小頻點數(shù)仍然在降低，最終收斂于42。因此，系統(tǒng)所需要的最小頻數(shù)應(yīng)該在42左右。

圖1 尋找最小可用頻點數(shù)的進化曲線

圖2給出了可用頻點數(shù)為51的仿真圖，采用DPSO算法時，經(jīng)過13次迭代，歷時4.3秒求得一個最優(yōu)解。采用本文算法時，經(jīng)過6次迭代，歷時3.9秒求得一個最優(yōu)解。本文采用的最優(yōu)漸進式變異算子增加了算法每次迭代的時間，但是減少了算法的迭代次數(shù)。綜合來說本文算法耗時略小于DPSO算法。由圖2可見，在2秒之前，DPSO算法和本文算法均未收斂，這是由于本文采用的粒子位置初始化方法增加了粒子初始化時的時間。

由表1可見，在頻點數(shù)為40時，本文算法仍能達到100%的收斂，即由本文算法求得的最小頻點數(shù)為40，遠遠優(yōu)于文獻 ［12］中求得的51個頻點。表1中，采用DPSO算法時，隨著可用頻點數(shù)的降低，算法的收斂率在逐漸降低，而算法的平均收斂代數(shù)并沒有明顯的變差，和其它算法相比，粒子群算法能夠迅速收斂。當(dāng)頻點數(shù)為51時，文獻 ［12］的平均收斂代數(shù)為54.5，DPSO算法的平均收斂代數(shù)為10.2，而本文算法的平均收斂代數(shù)為僅為5.5。采用了本文的IDPSO算法后，收斂率得到了顯著的提升，收斂代數(shù)也略有提高。本文中參數(shù)C需要合理的設(shè)置，C設(shè)置的過大在每一代進化中都要對最優(yōu)個體進行變異操作，必然會增加算法的運算時間，C設(shè)置的過小就不能使粒子跳出局部最優(yōu)值。

圖2 可用頻點數(shù)為51的仿真

表1 算法仿真結(jié)果比較

5 結(jié)束語

本文對離散粒子群算法做了改進，在每代最優(yōu)粒子中引入最優(yōu)漸進式變異算子，增加了粒子的多樣性，提高了算法的抗早熟能力。采用了最小間距編碼，壓縮了求解空間，加快了算法收斂。將改進的離散粒子群算法用于頻率分配問題上，仿真結(jié)果表明此算法能夠較好的解決該問題，在收斂率和收斂速度上優(yōu)于離散粒子群算法和混洗蛙跳算法。

文中參數(shù)C需要合理的設(shè)置，C設(shè)置過大會增加算法的運行時間，C設(shè)置的過小會降低算法的抗早熟能力。簡單合理的設(shè)置參數(shù)C是一項值得進一步研究的問題。

［1］ZHANG Chunfang，CHEN Juan.Solving frequency assignment problem using an adaptive multi colony ant algorithm ［J］.Mini－Micro Systems，2006，27 （5）：837－741 （in Chinese）.［章春芳，陳娟.求解頻率分配問題的自適應(yīng)的多種群蟻群算法 ［J］.小型微型計算機系統(tǒng)，2006，27 （5）：837－741.］

［2］ZHU Xiaojin，CHEN Yanchun，SHAO Yong，et al.Stepped annealing chaotic neural network model for the channel assignment problem ［J］.Journal on Communications，2008，29（5）：122－127 （in Chinese）. ［朱曉錦，陳艷春，邵勇，等.面向信道分配的分段退火混沌神經(jīng)網(wǎng)絡(luò)模型 ［J］.通信學(xué)報，2008，29 （5）：122－127.］

［3］SAN Joserevuelta L M.A new adaptive genetic algorithm for fixed channel assignment ［J］.Information Sciences，2007（177）：2655－2678.

［4］KIM Visale，LIU Wei，CHEN Xiaohui，et al.Distributed constraint satisfaction of an improved channel assignment approach in cellular network ［J］.Computer Science，2012，39（6）：81－83 （in Chinese）. ［韋沙，劉威，陳小惠，等.蜂窩網(wǎng)中基于分布式約束滿足算法的改進信道分配 ［J］.計算機科學(xué)，2012，39 （6）：81－83.］

［5］XU Junjie，XIN Zhanhong.A frequency assignment approach based on microcanonical annealing algorithm ［J］.Journal of Beijing University of Posts and Telecommunications，2007，30 （2）：67－70（in Chinese）.［徐俊杰，忻展紅.基于微正則退火的頻率分配方法 ［J］.北京郵電大學(xué)學(xué)報，2007，30 （2）：67－70.］

［6］YU Shicai，WEI Xingang.Channel assignment strategy combining guard channel with queuing ［J］.Computer Engineering and Applications，2012，48 （1）：112－113 （in Chinese）. ［於時才，魏鑫剛.保護信道和排隊相結(jié)合的信道分配策略 ［J］.計算機工程與應(yīng)用，2012，48 （1）：112－113.］

［7］JIANG Fu，PENG Jun.Dynamic channel assignment based on swarm intelligence in emergency communication ［J］.Application Research of Computers，2012，29 （6）：2293－2296 （in Chinese）.［蔣富，彭軍.應(yīng)急通信系統(tǒng)中基于集群智能的動態(tài) 信 道 分 配 ［J］. 計 算 機 應(yīng) 用 研 究，2012，29 （6）：2293－2296.］

［8］Benameur L，Alami J，El Imrani A.A new discrete particle swarm model for the frequency assignment problem ［C］／／IEEE International Conference on Computer Systems and Applications，2009：139－144.

［9］GAO Guang’en，LIU Quanli，WANG Wei.Multi－channel assignment algorithm of industrial wireless networks based on discrete particle swarming optimization ［J］.Control and Decision，2012，27 （5）：697－702 （in Chinese）. ［高廣恩，劉全利，王偉.基于離散粒子群優(yōu)化的工業(yè)無線網(wǎng)多信道分配算法 ［J］.控制與決策，2012，27 （5）：697－702.］

［10］ZHONG Xiangyuan，JIN Min，ZHONG Xiangqian，et al.Channel assignment in cellular network based on self－adaptive genetic algorithm ［J］.Computer Enginee－ring，2010，36（17）：189－191 （in Chinese）.［仲向遠，金敏，仲向前，等.基于自適應(yīng)遺傳算法的蜂窩網(wǎng)絡(luò)信道分配 ［J］.計算機工程，2010，36 （17）：189－191.］

［11］LIU Hongbo，WANG Xiukun，TAN Guozhen.Convergence analysis of particle swarm optimization and its improved algorithm based on chaos ［J］.Control and Decision，2006，21（6）：636－640 （in Chinese）.［劉洪波，王秀坤，譚國真.粒子群優(yōu)化算法的收斂性分析及其混沌改進算法 ［J］.控制與決策，2006，21 （6）：636－640.］

［12］HE Di，JIA Zhenhong.Frequency allocation approach based on shuffled frog－leaping algorithm ［J］.Computer Engineering，2011，37 （21）：133－135 （in Chinese）. ［何迪，賈振紅.基于混洗蛙跳算法的頻率分配方法 ［J］.計算機工程，2011，37 （21）：133－135.］