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