分層優(yōu)化網(wǎng)絡資源規(guī)劃方法.doc

分層優(yōu)化網(wǎng)絡資源規(guī)劃方法介紹隨著對移動通信業(yè)務需求的巨大增長，系統(tǒng)設計優(yōu)化和無線網(wǎng)絡規(guī)劃的問題變得越來越重要。雖然在移動蜂窩網(wǎng)絡規(guī)劃領域作了很多關于覆蓋分析，信道分配，路由選擇和傳播等方面的研究，但在關于成本有效系統(tǒng)設計的網(wǎng)絡規(guī)劃方面的研究卻不多1-5。實際上，在復雜的移動通信設計中必須考慮很多因數(shù)，如系統(tǒng)性能，系統(tǒng)容量，小區(qū)覆蓋，話務量，地形和傳播特征等。關于小區(qū)數(shù)量，小區(qū)位置，基站和移動單元的設計參數(shù)及信道分配的決定必須根據(jù)相互之間的關系作出。小區(qū)的位置可以根據(jù)給定的小區(qū)數(shù)量，覆蓋性能，話務分布和傳播環(huán)境來確定?；竞鸵苿訂卧脑O計參數(shù)必須要等到小區(qū)的部署全部完成后才能具體化。最后，在話務和避免干擾等方面能改善系統(tǒng)性能的信道分配6-8只有在移動蜂窩網(wǎng)絡的結構被詳細說明后才能決定。在決定任何通信系統(tǒng)經(jīng)濟上的可行性時成本都是一個關鍵因素。一個好的設計方法應該能在諸如網(wǎng)絡性能標準，話務量和技術升級等因素中進行權衡，使成本最優(yōu)化9。至今已有幾個商用軟件包被成功應用于移動蜂窩系統(tǒng)的網(wǎng)絡規(guī)劃中，如plaNET軟件。但不管怎樣，它們在規(guī)劃中都沒有直接包括金融上的規(guī)劃或者考慮成本。另一方面，如Analysis STEM建模系統(tǒng)等的一些軟件是決策支持工具以獲得金融模型并提供蜂窩移動系統(tǒng)的成本分析。但在它們的成本模型中又沒有考慮網(wǎng)絡規(guī)劃。這篇論文試圖同時考慮成本和網(wǎng)絡規(guī)劃因數(shù)以填補這個缺口。這種唯一的組合對移動網(wǎng)絡業(yè)務的供應商有極大的意義。它發(fā)展了最優(yōu)化的網(wǎng)絡規(guī)劃方法，在系統(tǒng)設計上既使總的系統(tǒng)成本最小化同時又保證了好的系統(tǒng)性能?？刹僮鞯难芯坎呗苑謱觾?yōu)化的規(guī)劃早已被成功應用于大規(guī)模制造系統(tǒng)的生產(chǎn)規(guī)劃和健康關心及服務系統(tǒng)的決策制定中10-12。在這些事例中，集合規(guī)劃通常是不可行的，因為對于大型的復雜系統(tǒng)的集合規(guī)劃模型通常不能被公式化或無法求解。在本論文中，我們描述了關于移動蜂窩通信系統(tǒng)設計的網(wǎng)絡規(guī)劃的分層特性，提出了一個分層優(yōu)化規(guī)劃方法(HOP)以確定無線網(wǎng)絡的結構，即小區(qū)的數(shù)量，小區(qū)的大小，小區(qū)的安置，天線增益及天線高度的參數(shù)和基站及移動單元的發(fā)射功率。一個組合優(yōu)化模型被推導出來以確定小區(qū)的最佳數(shù)量和基站的最佳位置使得在總的系統(tǒng)成本最小化的同時又能保證良好的覆蓋質(zhì)量和話務性能。規(guī)劃模型是一個有難度的組合優(yōu)化問題13。諸如分支界限法和動態(tài)規(guī)劃法之類的優(yōu)化算法不能在合理的時間內(nèi)求得優(yōu)化解13。因為牽涉到很多變量和復雜的約束，被用來解決大型組合優(yōu)化問題的分解法和拉格朗日松馳法14可能也無法應用到規(guī)劃模型中。在本論文中，一個建立在模擬退火(SA)基礎上的算法被推導出來用于解決此問題，并在合理的計算量內(nèi)求得了逼近的最優(yōu)結果。本論文的安排如下。在第二節(jié)，我們描述了蜂窩無線網(wǎng)絡規(guī)劃問題。第三節(jié)提出了解決這個問題的分層優(yōu)化規(guī)劃方法。在這一節(jié)還提出了組合優(yōu)化模型和模擬退火算法。最后，在第四節(jié)給出了用HOP方法實現(xiàn)新加坡的蜂窩移動通信服務系統(tǒng)的網(wǎng)絡規(guī)劃的模擬結果。問題陳訴如圖1所示，假如我們想要發(fā)展一個蜂窩移動通信系統(tǒng)為新加坡地區(qū)提供服務。整個地區(qū)將覆蓋三種類型的土地：市區(qū)，郊區(qū)和農(nóng)村。我們需要考慮非一致的話務分布：話務高峰通常在市中心，局部話務高峰在郊區(qū)中心。給定與覆蓋性能相關的地區(qū)覆蓋概率。邊界處的定位概率和覆蓋邊界處接收信號強度的門限電平可以從覆蓋概率和要求的信號強度，即載干比C/N2中推導得出。服務等級被設定為在忙時發(fā)起呼叫的阻塞概率。為滿足業(yè)務要求在系統(tǒng)中采用了頻率復用方案。問題是怎樣設計一個最優(yōu)網(wǎng)絡結構，即確定小區(qū)的數(shù)量，小區(qū)的大小，每個基站的位置和基站及移動單元的參數(shù)，以保證達到要求的性能目標，并使總的系統(tǒng)成本最小化。基站設備的成本是由機器設備及安裝，天線，建筑物及鐵塔和發(fā)射機及收信機等的成本決定的。為了設計這樣一個系統(tǒng)，必須考慮許多因素1,9，需要作出許多不同層次的決策。涉及的主要因素如下：系統(tǒng)性能的詳述，小區(qū)的覆蓋，話務分布，地形，傳播數(shù)據(jù)和系統(tǒng)成本因素。所有的這些因素相互影響，它們之間的復雜關系需要確定。由于系統(tǒng)的復雜性，在實際中網(wǎng)絡規(guī)劃過程是分層次的。規(guī)劃活動包括：性能的說明和分析，從小區(qū)的數(shù)量及小區(qū)的位置方面來說的形式上的小區(qū)規(guī)劃，和關于射頻小區(qū)參數(shù)的設置及信道分配的詳細小區(qū)設計。網(wǎng)絡規(guī)劃和設計方法我們提出了蜂窩移動通信網(wǎng)絡設計的三層HOP方法。網(wǎng)絡規(guī)劃的三層結構如圖2 所示。在第一層，決定了小區(qū)數(shù)量的上界和相應的小區(qū)覆蓋范圍。HOP的輸入?yún)?shù)如下：忙時的話務負荷，覆蓋要求和整個服務區(qū)域的地形特征。并選擇典型情況下的傳播參數(shù)。任務為用最小的小區(qū)數(shù)量覆蓋整個區(qū)域并滿足平均話務需求。在第二層，小區(qū)的數(shù)量和最佳的小區(qū)位置由大型的組合優(yōu)化模型決定。模型的規(guī)劃目標是使總的系統(tǒng)成本最小化，同時確保覆蓋的質(zhì)量，并努力符合非一致話務負載的要求。我們考慮到了不同用戶的話務密度和不同類型服務區(qū)域的地形特征。如圖1 所示，整個區(qū)域被劃分為市區(qū)，郊區(qū)和農(nóng)村。這些區(qū)域進一步被劃分為更小的網(wǎng)格。環(huán)境結構方面的信息，用戶密度和每個網(wǎng)格的平均俯角等都可以從地理信息系統(tǒng)(GIS)的數(shù)據(jù)庫里得到。詳細規(guī)劃在第三層進行，每個小區(qū)的具體參數(shù)，如天線模型及其增益，發(fā)射功率，天線高度和信道利用率等都在這一層設置。最后，把成本估計出來。規(guī)劃過程的總體系統(tǒng)性能很大程度上取決于不同層次上的不同活動和決策相結合的程度。如圖2所示，決策必須在雙向上相互調(diào)整和加強。為了獲得這個HOP方法和最優(yōu)成本模型，需要考慮幾個復雜的關系：覆蓋率的要求，小區(qū)的覆蓋范圍和小區(qū)邊界信號強度之間的關系2；傳播損失和具體的人造建筑物及地形外表之間的關系17；設備和成本之間的關系。傳播損失可以用Hata傳播模型預測18。Hata模型刻劃了對于市區(qū)，郊區(qū)和農(nóng)村等地形是準光滑或不規(guī)則的不同環(huán)境下無線傳播的特性。在蜂窩系統(tǒng)的設計中這個模型廣泛應用于預測不同環(huán)境下的路徑損失1719。關于市區(qū)內(nèi)基本傳輸損耗的Hata公式由下式給出：Lu (db) = 69.55 + 26.26log(f) - 13.82log() - a() + 44.9 - 6.55log()log(d) (1)其中移動臺天線高度的校正因子a()為：對于中小城市，a()=1.1log(f)-0.7-1.56log(f)-0.8；對于大城市，a()=3.2log(11.75)-4.97，且頻率f400MHz。郊區(qū)和農(nóng)村的傳播損失Lsu和Lrqo由下式給出：Lsu = Lu - 2log(f/28) - 5.4 (2)Lrqo = Lu 4.78log(f) + 18.33log(f) 35.94 (3)Hata公式適用的范圍為頻率f在150 MHz到1000 MHz之間，基站天線高度介于30m和100m之間，移動臺天線高度介于1m和10m之間，距離d的變化范圍為從1km到20km。在以下各節(jié)中，將給出HOP方法每一層的細節(jié)。A. 第一層：小區(qū)數(shù)量和小區(qū)大小的最初決定首先，根據(jù)整個地區(qū)的覆蓋性能和平均話務需求決定需要的最小基站數(shù)。為了確定系統(tǒng)設計中需要的小區(qū)數(shù)的上界，這個最小的基站數(shù)是在最差的情況下計算的的。在此我們?nèi)⌒^(qū)復用因子k=7，并給定地區(qū)覆蓋概率和用戶阻塞率。把覆蓋區(qū)域?qū)σ苿釉拕樟康囊罂紤]為在忙時由在此區(qū)域內(nèi)的移動單元發(fā)起的所有呼叫嘗試。它是根據(jù)覆蓋區(qū)域內(nèi)車輛的交通流量來預測的。給定預估的呼叫嘗試率，該區(qū)域的話務負載就轉化為忙時在此區(qū)域內(nèi)的移動用戶數(shù)。我們定義以下符號： 根據(jù)每個小區(qū)的信道數(shù)和給定的阻塞率得到的每個小區(qū)可以提供的話務量(用戶數(shù)/小時)。 整個服務區(qū)的總話務量(用戶數(shù)/小時)。 覆蓋邊界處的接收信號強度的門限電平。 射頻輸出的峰值功率(dbW)。 發(fā)射天線的輸入功率(dbW)。 接收天線的接收功率(dbW)。, 分別為基站和移動單元的天線增益(db)。, 分別為基站和移動單元的天線高度。d 小區(qū)的平均輻射半徑(km)。S 服務區(qū)的總面積(km)。首先考慮覆蓋性能。從發(fā)射機到接收機射頻功率的鏈接預算資源由下列方程給出1，9： = + L(d) + (4) = l (5)其中L(d)是傳輸損耗(db)，而l是絕緣體，組合器和射頻電纜的復合損耗。整個地區(qū)小區(qū)數(shù)量的上界由關于市區(qū)的Hata傳播模型決定。關于郊區(qū)和農(nóng)村的模型將在規(guī)劃的下一層考慮。假設有下列條件1，9：= 10W，=30m，=3m，=12dBi，= 2dBi，l = 4dB，f = 900MHz。則關于傳播損失L的公式(1)變?yōu)椋?L(d) = 123.73 + 35.22log(d) (6)為保證滿足覆蓋要求，我們有 = 73.73 35.22log(d) (7)即 log(d) log(d) = ( - 73.73)/35.22 (8)其中d是在大城市市區(qū)環(huán)境下最大的小區(qū)輻射半徑。那么，小區(qū)的最小數(shù)量為： (9)如果由業(yè)務量的分布情況來確定覆蓋區(qū)圖形，小區(qū)數(shù)量就由話務量決定1。在這種情況下，小區(qū)的最小數(shù)量為： (10)由此可以給出小區(qū)的最小數(shù)量為： n = max， (11)在最初的系統(tǒng)設計中，我們設n為小區(qū)數(shù)量的上界以得到成本有效的設計。在給定小區(qū)數(shù)量后，平均小區(qū)輻射半徑由d = 決定。B. 第二層：最優(yōu)小區(qū)位置和小區(qū)數(shù)量及小區(qū)大小的確定在這一層，考慮了整個區(qū)域的非一致話務分布。有關地形結構和環(huán)境的數(shù)據(jù)，話務密度，俯角均存儲在每個網(wǎng)格中。一旦已知小區(qū)數(shù)量的上界，下一步就是要確定那一個網(wǎng)格屬于那一個小區(qū)。進而就確定了小區(qū)的數(shù)量，不同的小區(qū)位置和小區(qū)大小。一般地，小區(qū)由相鄰的具有相同分類的幾個網(wǎng)格組成。在本論文中，建立了一個組合優(yōu)化模型來確定那個網(wǎng)格屬于那個小區(qū)和基站參數(shù)的最優(yōu)值。我們考慮關于覆蓋標準的“硬”約束和非一致話務需求的“軟”約束，“軟”約束可被放松且可通過補償項合并入目標函數(shù)。模型的目標是使整個系統(tǒng)成本最小化。在輕話務量條件下，小區(qū)的數(shù)量可進一步減少。1)經(jīng)濟優(yōu)化模型的數(shù)學闡述：為了闡明這個問題，我們引入以下決策變量：= 1，若網(wǎng)格i屬于小區(qū)k = 1，若小區(qū)k被網(wǎng)格占據(jù)0， 若網(wǎng)格i不屬于小區(qū)k 0，若小區(qū)k內(nèi)沒有網(wǎng)格(節(jié)約一個小區(qū))進一步，我們定義如下： 1， 網(wǎng)格i內(nèi)的市區(qū)結構 = 2， 網(wǎng)格i內(nèi)的郊區(qū)結構 3， 網(wǎng)格i內(nèi)的農(nóng)村結構 網(wǎng)格i內(nèi)的話務密度(用戶數(shù)/小時)。 n 總的小區(qū)數(shù)。m 總的網(wǎng)格數(shù)。 交換機房，硬件和安裝的固定成本。 基站內(nèi)的硬件和安裝的成本。 考慮其增益的天線的成本系數(shù)。 考慮其發(fā)射功率的發(fā)射機和接收機的成本系數(shù)。 小區(qū)k內(nèi)的基站發(fā)射功率，且，其中和分別是其相應的上界和下界。 分別為小區(qū)k內(nèi)的基站和移動單元的天線增益，且其中和分別是其相應的上界和下界。 分別為小區(qū)k內(nèi)的基站和移動單元的天線高度。 小區(qū)k的輻射半徑。 網(wǎng)格的范圍。 關于蜂窩移動通信網(wǎng)絡的經(jīng)濟優(yōu)化模型(EOM)闡述如下： EOM：min =+(+) (12)受約束于 k=1,2, ,n (13) k=1,2, ,n (14) k=1,2, ,n; i,=1,2, ,m;i (15) i=1,2, ,m (16) k=1,2, ,n (17) (-1) 0 k=1,2, ,n (18) - 1 k=1,2, ,n (19) 對所有i和k，,的值為1或0 (20)在EOM模型中，目標函數(shù)(12)的目的是最小化總的系統(tǒng)成本。約束(13)用來確保覆蓋性能。約束(14)保證設計滿足非一致話務量的要求。約束(15)(17)確保小區(qū)由具有相同結構且彼此相鄰的網(wǎng)格組成。約束(18)(20)給出了和之間的關系，即當0時，0；當0時，1。信號傳播損耗通過Hata預測模型進行計算。根據(jù)以下條件1,9：= 10W，=30m，=3m，=12dBi，= 2dBi，l = 4dB，f = 900MHz，我們有： 35.22log() (21)其中當小區(qū)k分別覆蓋市區(qū)、郊區(qū)和農(nóng)村區(qū)域時，123.73,113.79和102.22。2)用模擬退火算法求解EOM模型：EOM模型是個有難度的組合優(yōu)化問題，因為在模型中有很多變量和復雜的約束13。沒有一種優(yōu)化算法能在合理的時間里求得最優(yōu)解。在文獻15和16中報導的建立在模擬退火(SA)基礎上的算法被用來解決這個問題，并在合理的時間內(nèi)求得了逼近最優(yōu)解。對于求解NP完全組合問題的逼近解來說模擬退火是種好方法13。它已被成功應用于某些領域，如計算機的優(yōu)化設計16，圖象處理，信道分配820和規(guī)劃布局問題。算法采用一種迭代方案，它模擬物理退火過程：加熱固體直到其融化，然后花最少的能量冷卻它使其結晶至基態(tài)。為了用模擬退火過程解決EOM問題，需要考慮下面四個方面：配置空間，成本函數(shù)，相鄰結構和冷卻進度表。a)配置空間：對于EOM模型，配置空間S是所有滿足覆蓋約束(13)和其它約束(15)-(20)可行解的集。b) 成本函數(shù)：在實際的系統(tǒng)設計中，首先要考慮覆蓋性能。對于給定的小區(qū)數(shù)量，由于非一致話務分布的存在，如果要滿足覆蓋和話務兩者的要求，沒有幾個可行解可被求得。因而引入話務約束(14)到目標函數(shù)，目標函數(shù)就從(12)變?yōu)樽钚』镜目傇O備成本和破壞話務負載后引起的總補償，即： (22)其中函數(shù)x=max(0,x)。因為(12)中的系統(tǒng)固定成本不影響EOM模型的最優(yōu)解，故在成本函數(shù)中不再包含這一項。c) 相鄰結構：用N(s)表示的解s的鄰域由在滿足約束(15)-(17)時，移動網(wǎng)格k從當前小區(qū)i到相鄰小區(qū)j時產(chǎn)生。d) 冷卻進度表：決定初始溫度t以確?？山邮苻D換與提議轉換之比的特定接受率接近115。這可以通過從一個小的正數(shù)t出發(fā)，迭代地變換它直到達到接受率來得到。Huang21用在某一溫度的成本分布的標準偏差來決定下個溫度的減小量，并提出下面的溫度遞減規(guī)則： (23)其中是在溫度t的成本分布的標準偏差；是發(fā)生在兩個連續(xù)溫度t和t之間的平均成本的減少量。為保持準平衡，當。的典型值0.7。在某個溫度平衡意味著齊次馬爾可夫鏈的固定成本分布的建立。Huang假設了一個關于平衡的成本的正態(tài)分布，它們的平均值和標準偏差都由馬爾可夫鏈估計而來。他們提出了完成固定分布檢查的平衡條件：一旦平衡建立，其成本限制在范圍內(nèi)可接受的轉換次數(shù)的比率將達到一個穩(wěn)定值erf()，其中介于平均成本(它被稱為次數(shù)內(nèi))和可接受轉換總次數(shù)之間，erf(x)是x的誤差函數(shù)22。的典型值為0.5，從而可得erf()0.38。兩個平衡參數(shù)，一個目標次數(shù)內(nèi)和一個最大容許偏差極限，都根據(jù)問題的大小建立。如果次數(shù)內(nèi)在容許偏差次數(shù)超過最大極限值以前達到了目標值，我們就認為保持了平衡21。對于我們的EOM問題，我們設置次數(shù)內(nèi) 0.38*(3*m*n)和最大容許偏差= 0.62*(3*m*n)。我們說取得了最后溫度，如果在那個溫度的馬而可夫鏈的整個軌跡里，最大和最小成本的差值等于在那個溫度的一次可接受轉換里的成本的最大一次變化。下列偽代碼程序描述了解決EOM問題的模擬退火過程(SAEOM)。解決EOM問題的模擬退火過程(SAEOM)：Begin 初始化()； k := 0； s := ； Repeat Until 平衡達到 do Begin 從N(s)產(chǎn)生； If () then s := Else If exp(f(s)-f()/t) random0,1) then s := End； k := k+1； 計算t； Until 停止準則成立End與Kirpatrick16提出的模擬退火技巧相比，這個用Huang方法21的新SA技巧能通過退火過程動態(tài)調(diào)節(jié)馬爾可夫鏈的長度達到平衡，退火需要的CPU時間也大大地下降了。C.詳細規(guī)劃和準確的成本估計在這一層，確定每個小區(qū)內(nèi)的基站位置，諸如天線塔高度，天線增益和發(fā)射功率等參數(shù)都進一步根據(jù)每個小區(qū)的地形不規(guī)則性的特征，表面覆蓋和環(huán)境進行調(diào)整。從上面兩層得到的結果已滿足了覆蓋性能，并試圖滿足話務要求。但不管怎樣，在某些小區(qū)的話務過載可能仍然存在。在這一層，可以用Hale6和Gamst23的信道分配策略來提供信道數(shù)的下界。把在7820中提到的固定和動態(tài)信道分配策略應用于蜂窩系統(tǒng)的網(wǎng)絡規(guī)劃以提供足夠的容量來為預期的話務量服務，并保持無線干擾到最小限度。如果系統(tǒng)性能在調(diào)整后達到了要求，最后的系統(tǒng)設計就確定了，也就可以估計出蜂窩系統(tǒng)的成本。否則在這一層的結果將反饋到第一層和第二層。然后重復整個過程。在這種情況下，可能需要增加小區(qū)的數(shù)量以滿足規(guī)定的服務質(zhì)量。模擬結果A.HOP模型的應用分層優(yōu)化方法被用來設計提供如圖1和圖3所示的為新加坡地區(qū)提供服務的蜂窩系統(tǒng)。在我們的研究中使用了模仿新加坡地形，話務分布和人口的數(shù)據(jù)。整個地區(qū)被分為三種類型和100個網(wǎng)格。表1列出了關于每個網(wǎng)格的話務密度和地面類型等信息。服務區(qū)域S有625km，每個網(wǎng)格的區(qū)域面積約為2.5*2.5 km。在系統(tǒng)設計中采用了7小區(qū)頻率復用模型。假設要達到90%的區(qū)域覆蓋率并且忙時初始呼叫的阻塞率5。當2.3時，相應于90的區(qū)域覆蓋率，邊界處的位置覆蓋75，其中是接收信號的慢衰落部分的標準偏差，是距離因子的指數(shù)2。對于給定的位置覆蓋概率和要求的C/N和C/I，設置邊界處的接收信號強度93dbm19。假設每個小區(qū)的信道數(shù)為45，平均通話時長為1.76min/call，呼叫嘗試率為0.9call/h，則每小區(qū)可提供的話務負載為39.6愛爾蘭，能為=(39.6*60)/(1.76*0.9)=1500subscribers/h的總移動單元數(shù)提供服務。首先，開始進行設計時先需要確定小區(qū)數(shù)的上界。從(4)(6)我們可得17，d3.53km。從(7)我們有29400/150020。同時考慮覆蓋和話務性能，我們選擇n = max(,) = 20。接著，來確定20個小區(qū)的安置，假設給出系統(tǒng)成本的標準化參數(shù)如下：=1000，=5.0，10.0，0.5?；竞鸵苿訂卧膮?shù)選擇如下9：對所有的小區(qū)k，。根據(jù)24和25，我們得到了天線成本和其增益及發(fā)射機(或接收機)成本和其發(fā)射功率之間的逼近線性關系。假設給出關于天線增益g的成本函數(shù)如下： = 40+Cag M 關于發(fā)射功率P的成本函數(shù)如下： = 60 + CtP M 其中M是一個大的正數(shù)。我們根據(jù)上面的具體參數(shù)應用模擬退火算法SAEOM來求解EOM問題。冷卻進度表的控制參數(shù)如下：初始接受率0.9，次數(shù)內(nèi)目標0.38*3*20*100，最大容許偏差= 0.62*(3*m*n)，最大生成極限4*MUB21。在HP-C180的UNIX系統(tǒng)上用C語言執(zhí)行了這個算法。圖3給出了一個初始可行解(初始設計)。具有相同陰影的相鄰網(wǎng)格組成一個小區(qū)?？傁到y(tǒng)成本為24349.68。圖4給出了用SAEOM算法求出的最優(yōu)解。這個最優(yōu)解是在用不同的初始可行解運行程序10次后才獲得的。最終設計fc(s)的鄰近最優(yōu)系統(tǒng)成本是20139.20。小區(qū)數(shù)進一步減少了6個。圖5顯示了收斂記錄，即用SAEOM算法求解EOM問題的退火曲線。退火需要的平均CPU時間為34.65分鐘。為了評估SA方法求得的解，我們把它與用Aarts和Korst15的本地搜索過程求得的最佳解和用隨機生成過程獲得的解比較。用本地搜索過程求得的最佳解為系統(tǒng)成本fc(s)20452.4和小區(qū)數(shù)n13。如成本函數(shù)(19)所示，每個小區(qū)的固定成本決定總系統(tǒng)成本。這意味著成本有效設計應該有較少的小區(qū)數(shù)和每個小區(qū)較高的平均話務負載。圖6和圖7分別表示用SAEON和本地搜索方法求得的最佳解中的話務量柱形圖。圖8表示在小區(qū)數(shù)也是13這種情況下，隨機生成過程獲得的解的話務量分布。虛線和實心條分別代表每個小區(qū)能提供的話務負載和需要的話務負載。從圖6-8，我們觀察到用SAEON求得的逼近最優(yōu)解在能提供的話務負載和需要的話務負載之間取得了好的折衷。與其它兩個過程相比，每個小區(qū)的話務負載也呈均勻分布。如圖4 的最終設計所示，這個設計能滿足覆蓋要求，同時也努力用最小的小區(qū)數(shù)和最佳的小區(qū)安置適應非一致話務負載。天線增益和發(fā)射功率的逼近最優(yōu)值可從最佳解中獲得。在最后一步，基站和移動單元的所有參數(shù)都要根據(jù)所在小區(qū)內(nèi)具體的地形數(shù)據(jù)和覆蓋特征進行調(diào)整。從上面兩層獲得的結果能滿足覆蓋的質(zhì)量要求，但并不能提供每個小區(qū)的所有預期話務量。在最后一層，Gamst23技巧被用來確定要分配的信道數(shù)下界。然后進一步應用Dugue-anton20的信道分配過程去滿足話務要求和避免干擾。B.SA算法的性能模擬退火方法SAEOM的性能研究