基于改進離散粒子群的蜂窩網絡信道分配

馮志強，賈振紅，許國軍

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

0 引 言

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

1 信道分配問題模型

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

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

2 離散粒子群算法

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

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

3 改進的離散粒子群算法

3.1 個體編碼

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

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

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

3.2 粒子的位置和速度

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

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

本文使用交換算子 （i，j）表示小區的當前信道i和即將要切換到的信道j，m個交換算子就構成了粒子的速度

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

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

3.3 最優漸進式變異算子

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

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

3.4 變異概率的確定

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

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

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

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

3.5 算法復雜度分析

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

3.6 粒子位置初始化

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

3.7 本文算法步驟

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

（2）根據式 （5）或式 （6）計算粒子的適應度，更新粒子的局部最優值和全局最優值。

（3）根據式 （11）判斷當前粒子是否出現聚集，若出現聚集按式 （12）的變異概率對最優粒子執行最優漸進式變異；若未出現聚集執行步驟 （4）。

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

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

（6）終止條件判斷，若已尋找到最優個體或者達到最大迭代次數，則算法結束，否則執行步驟 （2）。

4 仿 真

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

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

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

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

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

圖2 可用頻點數為51的仿真

表1 算法仿真結果比較

5 結束語

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

文中參數C需要合理的設置，C設置過大會增加算法的運行時間，C設置的過小會降低算法的抗早熟能力。簡單合理的設置參數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）.［章春芳，陳娟.求解頻率分配問題的自適應的多種群蟻群算法 ［J］.小型微型計算機系統，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］.通信學報，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）. ［韋沙，劉威，陳小惠，等.蜂窩網中基于分布式約束滿足算法的改進信道分配 ［J］.計算機科學，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］.北京郵電大學學報，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）. ［於時才，魏鑫剛.保護信道和排隊相結合的信道分配策略 ［J］.計算機工程與應用，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）.［蔣富，彭軍.應急通信系統中基于集群智能的動態 信 道 分 配 ［J］. 計 算 機 應 用 研 究，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）. ［高廣恩，劉全利，王偉.基于離散粒子群優化的工業無線網多信道分配算法 ［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）.［仲向遠，金敏，仲向前，等.基于自適應遺傳算法的蜂窩網絡信道分配 ［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）.［劉洪波，王秀坤，譚國真.粒子群優化算法的收斂性分析及其混沌改進算法 ［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.］