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

1、低成本的蜂窩移動(dòng)通信系統(tǒng)：分層優(yōu)化網(wǎng)絡(luò)資源規(guī)劃方法摘要：本論文涉及蜂窩移動(dòng)通信系統(tǒng)的設(shè)計(jì)優(yōu)化和無(wú)線網(wǎng)絡(luò)資源的規(guī)劃。在移動(dòng)網(wǎng)絡(luò)規(guī)劃中需要考慮的關(guān)鍵因數(shù)是成本。由于在大型的系統(tǒng)設(shè)計(jì)中必須考慮諸如系統(tǒng)性能，地形特征，基站參數(shù)和成本等很多因素，故分層優(yōu)化規(guī)劃方法(HOP)得到了應(yīng)用。在此我們提出了設(shè)計(jì)蜂窩移動(dòng)系統(tǒng)的三層優(yōu)化方法。它能確定小區(qū)的數(shù)量，小區(qū)的安置和具體的基站參數(shù)以使整個(gè)系統(tǒng)的成本最小化并符合所要求的系統(tǒng)性能。我們把問(wèn)題闡述為一個(gè)大型的組合優(yōu)化模型，通過(guò)此模型確定小區(qū)的最優(yōu)數(shù)量并選擇最佳的基站位置。模擬退火方法被用來(lái)解決這個(gè)困難的組合問(wèn)題。模擬結(jié)果證明了HOP方法在無(wú)線網(wǎng)絡(luò)規(guī)劃中的可行性和有

2、效性。關(guān)鍵詞：蜂窩移動(dòng)通信系統(tǒng)，最優(yōu)化，無(wú)線網(wǎng)絡(luò)規(guī)劃，模擬退火介紹隨著對(duì)移動(dòng)通信業(yè)務(wù)需求的巨大增長(zhǎng)，系統(tǒng)設(shè)計(jì)優(yōu)化和無(wú)線網(wǎng)絡(luò)規(guī)劃的問(wèn)題變得越來(lái)越重要。雖然在移動(dòng)蜂窩網(wǎng)絡(luò)規(guī)劃領(lǐng)域作了很多關(guān)于覆蓋分析，信道分配，路由選擇和傳播等方面的研究，但在關(guān)于成本有效系統(tǒng)設(shè)計(jì)的網(wǎng)絡(luò)規(guī)劃方面的研究卻不多1-5。實(shí)際上，在復(fù)雜的移動(dòng)通信設(shè)計(jì)中必須考慮很多因數(shù)，如系統(tǒng)性能，系統(tǒng)容量，小區(qū)覆蓋，話務(wù)量，地形和傳播特征等。關(guān)于小區(qū)數(shù)量，小區(qū)位置，基站和移動(dòng)單元的設(shè)計(jì)參數(shù)及信道分配的決定必須根據(jù)相互之間的關(guān)系作出。小區(qū)的位置可以根據(jù)給定的小區(qū)數(shù)量，覆蓋性能，話務(wù)分布和傳播環(huán)境來(lái)確定?；竞鸵苿?dòng)單元的設(shè)計(jì)參數(shù)必須要等到小區(qū)的

3、部署全部完成后才能具體化。最后，在話務(wù)和避免干擾等方面能改善系統(tǒng)性能的信道分配6-8只有在移動(dòng)蜂窩網(wǎng)絡(luò)的結(jié)構(gòu)被詳細(xì)說(shuō)明后才能決定。在決定任何通信系統(tǒng)經(jīng)濟(jì)上的可行性時(shí)成本都是一個(gè)關(guān)鍵因素。一個(gè)好的設(shè)計(jì)方法應(yīng)該能在諸如網(wǎng)絡(luò)性能標(biāo)準(zhǔn)，話務(wù)量和技術(shù)升級(jí)等因素中進(jìn)行權(quán)衡，使成本最優(yōu)化9。至今已有幾個(gè)商用軟件包被成功應(yīng)用于移動(dòng)蜂窩系統(tǒng)的網(wǎng)絡(luò)規(guī)劃中，如plaNET軟件。但不管怎樣，它們?cè)谝?guī)劃中都沒(méi)有直接包括金融上的規(guī)劃或者考慮成本。另一方面，如Analysis STEM建模系統(tǒng)等的一些軟件是決策支持工具以獲得金融模型并提供蜂窩移動(dòng)系統(tǒng)的成本分析。但在它們的成本模型中又沒(méi)有考慮網(wǎng)絡(luò)規(guī)劃。這篇論文試圖同時(shí)考慮成

4、本和網(wǎng)絡(luò)規(guī)劃因數(shù)以填補(bǔ)這個(gè)缺口。這種唯一的組合對(duì)移動(dòng)網(wǎng)絡(luò)業(yè)務(wù)的供應(yīng)商有極大的意義。它發(fā)展了最優(yōu)化的網(wǎng)絡(luò)規(guī)劃方法，在系統(tǒng)設(shè)計(jì)上既使總的系統(tǒng)成本最小化同時(shí)又保證了好的系統(tǒng)性能。可操作的研究策略分層優(yōu)化的規(guī)劃早已被成功應(yīng)用于大規(guī)模制造系統(tǒng)的生產(chǎn)規(guī)劃和健康關(guān)心及服務(wù)系統(tǒng)的決策制定中10-12。在這些事例中，集合規(guī)劃通常是不可行的，因?yàn)閷?duì)于大型的復(fù)雜系統(tǒng)的集合規(guī)劃模型通常不能被公式化或無(wú)法求解。在本論文中，我們描述了關(guān)于移動(dòng)蜂窩通信系統(tǒng)設(shè)計(jì)的網(wǎng)絡(luò)規(guī)劃的分層特性，提出了一個(gè)分層優(yōu)化規(guī)劃方法(HOP)以確定無(wú)線網(wǎng)絡(luò)的結(jié)構(gòu)，即小區(qū)的數(shù)量，小區(qū)的大小，小區(qū)的安置，天線增益及天線高度的參數(shù)和基站及移動(dòng)單元的發(fā)射功

5、率。一個(gè)組合優(yōu)化模型被推導(dǎo)出來(lái)以確定小區(qū)的最佳數(shù)量和基站的最佳位置使得在總的系統(tǒng)成本最小化的同時(shí)又能保證良好的覆蓋質(zhì)量和話務(wù)性能。規(guī)劃模型是一個(gè)有難度的組合優(yōu)化問(wèn)題13。諸如分支界限法和動(dòng)態(tài)規(guī)劃法之類(lèi)的優(yōu)化算法不能在合理的時(shí)間內(nèi)求得優(yōu)化解13。因?yàn)闋可娴胶芏嘧兞亢蛷?fù)雜的約束，被用來(lái)解決大型組合優(yōu)化問(wèn)題的分解法和拉格朗日松馳法14可能也無(wú)法應(yīng)用到規(guī)劃模型中。在本論文中，一個(gè)建立在模擬退火(SA)基礎(chǔ)上的算法被推導(dǎo)出來(lái)用于解決此問(wèn)題，并在合理的計(jì)算量?jī)?nèi)求得了逼近的最優(yōu)結(jié)果。本論文的安排如下。在第二節(jié)，我們描述了蜂窩無(wú)線網(wǎng)絡(luò)規(guī)劃問(wèn)題。第三節(jié)提出了解決這個(gè)問(wèn)題的分層優(yōu)化規(guī)劃方法。在這一節(jié)還提出了組合優(yōu)

6、化模型和模擬退火算法。最后，在第四節(jié)給出了用HOP方法實(shí)現(xiàn)新加坡的蜂窩移動(dòng)通信服務(wù)系統(tǒng)的網(wǎng)絡(luò)規(guī)劃的模擬結(jié)果。問(wèn)題陳訴如圖1所示，假如我們想要發(fā)展一個(gè)蜂窩移動(dòng)通信系統(tǒng)為新加坡地區(qū)提供服務(wù)。整個(gè)地區(qū)將覆蓋三種類(lèi)型的土地：市區(qū)，郊區(qū)和農(nóng)村。我們需要考慮非一致的話務(wù)分布：話務(wù)高峰通常在市中心，局部話務(wù)高峰在郊區(qū)中心。給定與覆蓋性能相關(guān)的地區(qū)覆蓋概率。邊界處的定位概率和覆蓋邊界處接收信號(hào)強(qiáng)度的門(mén)限電平可以從覆蓋概率和要求的信號(hào)強(qiáng)度，即載干比C/N2中推導(dǎo)得出。服務(wù)等級(jí)被設(shè)定為在忙時(shí)發(fā)起呼叫的阻塞概率。為滿足業(yè)務(wù)要求在系統(tǒng)中采用了頻率復(fù)用方案。問(wèn)題是怎樣設(shè)計(jì)一個(gè)最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)，即確定小區(qū)的數(shù)量，小區(qū)的大小，

7、每個(gè)基站的位置和基站及移動(dòng)單元的參數(shù)，以保證達(dá)到要求的性能目標(biāo)，并使總的系統(tǒng)成本最小化?；驹O(shè)備的成本是由機(jī)器設(shè)備及安裝，天線，建筑物及鐵塔和發(fā)射機(jī)及收信機(jī)等的成本決定的。為了設(shè)計(jì)這樣一個(gè)系統(tǒng)，必須考慮許多因素1,9，需要作出許多不同層次的決策。涉及的主要因素如下：系統(tǒng)性能的詳述，小區(qū)的覆蓋，話務(wù)分布，地形，傳播數(shù)據(jù)和系統(tǒng)成本因素。所有的這些因素相互影響，它們之間的復(fù)雜關(guān)系需要確定。由于系統(tǒng)的復(fù)雜性，在實(shí)際中網(wǎng)絡(luò)規(guī)劃過(guò)程是分層次的。規(guī)劃活動(dòng)包括：性能的說(shuō)明和分析，從小區(qū)的數(shù)量及小區(qū)的位置方面來(lái)說(shuō)的形式上的小區(qū)規(guī)劃，和關(guān)于射頻小區(qū)參數(shù)的設(shè)置及信道分配的詳細(xì)小區(qū)設(shè)計(jì)。網(wǎng)絡(luò)規(guī)劃和設(shè)計(jì)方法我們提出了蜂

8、窩移動(dòng)通信網(wǎng)絡(luò)設(shè)計(jì)的三層HOP方法。網(wǎng)絡(luò)規(guī)劃的三層結(jié)構(gòu)如圖2 所示。在第一層，決定了小區(qū)數(shù)量的上界和相應(yīng)的小區(qū)覆蓋范圍。HOP的輸入?yún)?shù)如下：忙時(shí)的話務(wù)負(fù)荷，覆蓋要求和整個(gè)服務(wù)區(qū)域的地形特征。并選擇典型情況下的傳播參數(shù)。任務(wù)為用最小的小區(qū)數(shù)量覆蓋整個(gè)區(qū)域并滿足平均話務(wù)需求。在第二層，小區(qū)的數(shù)量和最佳的小區(qū)位置由大型的組合優(yōu)化模型決定。模型的規(guī)劃目標(biāo)是使總的系統(tǒng)成本最小化，同時(shí)確保覆蓋的質(zhì)量，并努力符合非一致話務(wù)負(fù)載的要求。我們考慮到了不同用戶的話務(wù)密度和不同類(lèi)型服務(wù)區(qū)域的地形特征。如圖1 所示，整個(gè)區(qū)域被劃分為市區(qū)，郊區(qū)和農(nóng)村。這些區(qū)域進(jìn)一步被劃分為更小的網(wǎng)格。環(huán)境結(jié)構(gòu)方面的信息，用戶密度和每

9、個(gè)網(wǎng)格的平均俯角等都可以從地理信息系統(tǒng)(GIS)的數(shù)據(jù)庫(kù)里得到。詳細(xì)規(guī)劃在第三層進(jìn)行，每個(gè)小區(qū)的具體參數(shù)，如天線模型及其增益，發(fā)射功率，天線高度和信道利用率等都在這一層設(shè)置。最后，把成本估計(jì)出來(lái)。規(guī)劃過(guò)程的總體系統(tǒng)性能很大程度上取決于不同層次上的不同活動(dòng)和決策相結(jié)合的程度。如圖2所示，決策必須在雙向上相互調(diào)整和加強(qiáng)。為了獲得這個(gè)HOP方法和最優(yōu)成本模型，需要考慮幾個(gè)復(fù)雜的關(guān)系：覆蓋率的要求，小區(qū)的覆蓋范圍和小區(qū)邊界信號(hào)強(qiáng)度之間的關(guān)系2；傳播損失和具體的人造建筑物及地形外表之間的關(guān)系17；設(shè)備和成本之間的關(guān)系。傳播損失可以用Hata傳播模型預(yù)測(cè)18。Hata模型刻劃了對(duì)于市區(qū)，郊區(qū)和農(nóng)村等地形是

10、準(zhǔn)光滑或不規(guī)則的不同環(huán)境下無(wú)線傳播的特性。在蜂窩系統(tǒng)的設(shè)計(jì)中這個(gè)模型廣泛應(yīng)用于預(yù)測(cè)不同環(huán)境下的路徑損失1719。關(guān)于市區(qū)內(nèi)基本傳輸損耗的Hata公式由下式給出：Lu (db) = 69.55 + 26.26·log(f) - 13.82·log() - a() + 44.9 - 6.55·log()·log(d) (1)其中移動(dòng)臺(tái)天線高度的校正因子a()為：對(duì)于中小城市，a()=1.1·log(f)-0.7·-1.56·log(f)-0.8；對(duì)于大城市，a()=3.2·log(11.75·)-4.97，且

11、頻率f400MHz。郊區(qū)和農(nóng)村的傳播損失Lsu和Lrqo由下式給出：Lsu = Lu - 2·log(f/28) - 5.4 (2)Lrqo = Lu 4.78·log(f) + 18.33·log(f) 35.94 (3)Hata公式適用的范圍為頻率f在150 MHz到1000 MHz之間，基站天線高度介于30m和100m之間，移動(dòng)臺(tái)天線高度介于1m和10m之間，距離d的變化范圍為從1km到20km。在以下各節(jié)中，將給出HOP方法每一層的細(xì)節(jié)。A. 第一層：小區(qū)數(shù)量和小區(qū)大小的最初決定首先，根據(jù)整個(gè)地區(qū)的覆蓋性能和平均話務(wù)需求決定需要的最小基站數(shù)。為了確定系統(tǒng)設(shè)

12、計(jì)中需要的小區(qū)數(shù)的上界，這個(gè)最小的基站數(shù)是在最差的情況下計(jì)算的的。在此我們?nèi)⌒^(qū)復(fù)用因子k=7，并給定地區(qū)覆蓋概率和用戶阻塞率。把覆蓋區(qū)域?qū)σ苿?dòng)話務(wù)量的要求考慮為在忙時(shí)由在此區(qū)域內(nèi)的移動(dòng)單元發(fā)起的所有呼叫嘗試。它是根據(jù)覆蓋區(qū)域內(nèi)車(chē)輛的交通流量來(lái)預(yù)測(cè)的。給定預(yù)估的呼叫嘗試率，該區(qū)域的話務(wù)負(fù)載就轉(zhuǎn)化為忙時(shí)在此區(qū)域內(nèi)的移動(dòng)用戶數(shù)。我們定義以下符號(hào)：根據(jù)每個(gè)小區(qū)的信道數(shù)和給定的阻塞率得到的每個(gè)小區(qū)可以提供的話務(wù)量(用戶數(shù)/小時(shí))。 整個(gè)服務(wù)區(qū)的總話務(wù)量(用戶數(shù)/小時(shí))。 覆蓋邊界處的接收信號(hào)強(qiáng)度的門(mén)限電平。 射頻輸出的峰值功率(dbW)。發(fā)射天線的輸入功率(dbW)。 接收天線的接收功率(dbW)。,

13、分別為基站和移動(dòng)單元的天線增益(db)。,分別為基站和移動(dòng)單元的天線高度。d 小區(qū)的平均輻射半徑(km)。S 服務(wù)區(qū)的總面積(km)。首先考慮覆蓋性能。從發(fā)射機(jī)到接收機(jī)射頻功率的鏈接預(yù)算資源由下列方程給出1，9： = + L(d) + (4) = l (5)其中L(d)是傳輸損耗(db)，而l是絕緣體，組合器和射頻電纜的復(fù)合損耗。整個(gè)地區(qū)小區(qū)數(shù)量的上界由關(guān)于市區(qū)的Hata傳播模型決定。關(guān)于郊區(qū)和農(nóng)村的模型將在規(guī)劃的下一層考慮。假設(shè)有下列條件1，9：= 10W，=30m，=3m，=12dBi，= 2dBi，l = 4dB，f = 900MHz。則關(guān)于傳播損失L的公式(1)變?yōu)椋篖(d) = 12

14、3.73 + 35.22·log(d) (6)為保證滿足覆蓋要求，我們有 = 73.73 35.22·log(d) (7)即 log(d) log(d) = ( -73.73)/35.22 (8)其中d是在大城市市區(qū)環(huán)境下最大的小區(qū)輻射半徑。那么，小區(qū)的最小數(shù)量為：(9)如果由業(yè)務(wù)量的分布情況來(lái)確定覆蓋區(qū)圖形，小區(qū)數(shù)量就由話務(wù)量決定1。在這種情況下，小區(qū)的最小數(shù)量為： (10)由此可以給出小區(qū)的最小數(shù)量為：n = max， (11)在最初的系統(tǒng)設(shè)計(jì)中，我們?cè)O(shè)n為小區(qū)數(shù)量的上界以得到成本有效的設(shè)計(jì)。在給定小區(qū)數(shù)量后，平均小區(qū)輻射半徑由d = 決定。B. 第二層：最優(yōu)小區(qū)位置和

15、小區(qū)數(shù)量及小區(qū)大小的確定在這一層，考慮了整個(gè)區(qū)域的非一致話務(wù)分布。有關(guān)地形結(jié)構(gòu)和環(huán)境的數(shù)據(jù)，話務(wù)密度，俯角均存儲(chǔ)在每個(gè)網(wǎng)格中。一旦已知小區(qū)數(shù)量的上界，下一步就是要確定那一個(gè)網(wǎng)格屬于那一個(gè)小區(qū)。進(jìn)而就確定了小區(qū)的數(shù)量，不同的小區(qū)位置和小區(qū)大小。一般地，小區(qū)由相鄰的具有相同分類(lèi)的幾個(gè)網(wǎng)格組成。在本論文中，建立了一個(gè)組合優(yōu)化模型來(lái)確定那個(gè)網(wǎng)格屬于那個(gè)小區(qū)和基站參數(shù)的最優(yōu)值。我們考慮關(guān)于覆蓋標(biāo)準(zhǔn)的“硬”約束和非一致話務(wù)需求的“軟”約束，“軟”約束可被放松且可通過(guò)補(bǔ)償項(xiàng)合并入目標(biāo)函數(shù)。模型的目標(biāo)是使整個(gè)系統(tǒng)成本最小化。在輕話務(wù)量條件下，小區(qū)的數(shù)量可進(jìn)一步減少。1)經(jīng)濟(jì)優(yōu)化模型的數(shù)學(xué)闡述：為了闡明這個(gè)問(wèn)題

16、，我們引入以下決策變量：= 1，若網(wǎng)格i屬于小區(qū)k = 1，若小區(qū)k被網(wǎng)格占據(jù)0， 若網(wǎng)格i不屬于小區(qū)k 0，若小區(qū)k內(nèi)沒(méi)有網(wǎng)格(節(jié)約一個(gè)小區(qū))進(jìn)一步，我們定義如下： 1， 網(wǎng)格i內(nèi)的市區(qū)結(jié)構(gòu) = 2， 網(wǎng)格i內(nèi)的郊區(qū)結(jié)構(gòu) 3， 網(wǎng)格i內(nèi)的農(nóng)村結(jié)構(gòu) 網(wǎng)格i內(nèi)的話務(wù)密度(用戶數(shù)/小時(shí))。 n 總的小區(qū)數(shù)。m 總的網(wǎng)格數(shù)。 交換機(jī)房，硬件和安裝的固定成本。 基站內(nèi)的硬件和安裝的成本。 考慮其增益的天線的成本系數(shù)。 考慮其發(fā)射功率的發(fā)射機(jī)和接收機(jī)的成本系數(shù)。 小區(qū)k內(nèi)的基站發(fā)射功率，且，其中和分別是其相應(yīng)的上界和下界。 分別為小區(qū)k內(nèi)的基站和移動(dòng)單元的天線增益，且其中和分別是其相應(yīng)的上界和下界。 分

17、別為小區(qū)k內(nèi)的基站和移動(dòng)單元的天線高度。 小區(qū)k的輻射半徑。 網(wǎng)格的范圍。 關(guān)于蜂窩移動(dòng)通信網(wǎng)絡(luò)的經(jīng)濟(jì)優(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

18、) 0 k=1,2,···,n (18) - 1 k=1,2,···,n (19) 對(duì)所有i和k，,的值為1或0 (20)在EOM模型中，目標(biāo)函數(shù)(12)的目的是最小化總的系統(tǒng)成本。約束(13)用來(lái)確保覆蓋性能。約束(14)保證設(shè)計(jì)滿足非一致話務(wù)量的要求。約束(15)(17)確保小區(qū)由具有相同結(jié)構(gòu)且彼此相鄰的網(wǎng)格組成。約束(18)(20)給出了和之間的關(guān)系，即當(dāng)0時(shí)，0；當(dāng)0時(shí)，1。信號(hào)傳播損耗通過(guò)Hata預(yù)測(cè)模型進(jìn)行計(jì)算。根據(jù)以下條件1,9：= 10W，=30m，=3m，=12dBi，= 2dBi，l = 4dB，f = 900MH

19、z，我們有： 35.22·log() (21)其中當(dāng)小區(qū)k分別覆蓋市區(qū)、郊區(qū)和農(nóng)村區(qū)域時(shí)，123.73,113.79和102.22。2)用模擬退火算法求解EOM模型：EOM模型是個(gè)有難度的組合優(yōu)化問(wèn)題，因?yàn)樵谀Ｐ椭杏泻芏嘧兞亢蛷?fù)雜的約束13。沒(méi)有一種優(yōu)化算法能在合理的時(shí)間里求得最優(yōu)解。在文獻(xiàn)15和16中報(bào)導(dǎo)的建立在模擬退火(SA)基礎(chǔ)上的算法被用來(lái)解決這個(gè)問(wèn)題，并在合理的時(shí)間內(nèi)求得了逼近最優(yōu)解。對(duì)于求解NP完全組合問(wèn)題的逼近解來(lái)說(shuō)模擬退火是種好方法13。它已被成功應(yīng)用于某些領(lǐng)域，如計(jì)算機(jī)的優(yōu)化設(shè)計(jì)16，圖象處理，信道分配820和規(guī)劃布局問(wèn)題。算法采用一種迭代方案，它模擬物理退火過(guò)程：

20、加熱固體直到其融化，然后花最少的能量冷卻它使其結(jié)晶至基態(tài)。為了用模擬退火過(guò)程解決EOM問(wèn)題，需要考慮下面四個(gè)方面：配置空間，成本函數(shù)，相鄰結(jié)構(gòu)和冷卻進(jìn)度表。a)配置空間：對(duì)于EOM模型，配置空間S是所有滿足覆蓋約束(13)和其它約束(15)-(20)可行解的集。b) 成本函數(shù)：在實(shí)際的系統(tǒng)設(shè)計(jì)中，首先要考慮覆蓋性能。對(duì)于給定的小區(qū)數(shù)量，由于非一致話務(wù)分布的存在，如果要滿足覆蓋和話務(wù)兩者的要求，沒(méi)有幾個(gè)可行解可被求得。因而引入話務(wù)約束(14)到目標(biāo)函數(shù)，目標(biāo)函數(shù)就從(12)變?yōu)樽钚』镜目傇O(shè)備成本和破壞話務(wù)負(fù)載后引起的總補(bǔ)償，即： (22)其中函數(shù)x=max(0,x)。因?yàn)?12)中的系統(tǒng)固定

21、成本不影響EOM模型的最優(yōu)解，故在成本函數(shù)中不再包含這一項(xiàng)。c) 相鄰結(jié)構(gòu)：用N(s)表示的解s的鄰域由在滿足約束(15)-(17)時(shí)，移動(dòng)網(wǎng)格k從當(dāng)前小區(qū)i到相鄰小區(qū)j時(shí)產(chǎn)生。d) 冷卻進(jìn)度表：決定初始溫度t以確?？山邮苻D(zhuǎn)換與提議轉(zhuǎn)換之比的特定接受率接近115。這可以通過(guò)從一個(gè)小的正數(shù)t出發(fā)，迭代地變換它直到達(dá)到接受率來(lái)得到。Huang21用在某一溫度的成本分布的標(biāo)準(zhǔn)偏差來(lái)決定下個(gè)溫度的減小量，并提出下面的溫度遞減規(guī)則：(23)其中是在溫度t的成本分布的標(biāo)準(zhǔn)偏差；是發(fā)生在兩個(gè)連續(xù)溫度t和t之間的平均成本的減少量。為保持準(zhǔn)平衡，當(dāng)。的典型值0.7。在某個(gè)溫度平衡意味著齊次馬爾可夫鏈的固定成本分

22、布的建立。Huang假設(shè)了一個(gè)關(guān)于平衡的成本的正態(tài)分布，它們的平均值和標(biāo)準(zhǔn)偏差都由馬爾可夫鏈估計(jì)而來(lái)。他們提出了完成固定分布檢查的平衡條件：一旦平衡建立，其成本限制在范圍內(nèi)可接受的轉(zhuǎn)換次數(shù)的比率將達(dá)到一個(gè)穩(wěn)定值erf()，其中介于平均成本(它被稱(chēng)為次數(shù)內(nèi))和可接受轉(zhuǎn)換總次數(shù)之間，erf(x)是x的誤差函數(shù)22。的典型值為0.5，從而可得erf()0.38。兩個(gè)平衡參數(shù)，一個(gè)目標(biāo)次數(shù)內(nèi)和一個(gè)最大容許偏差極限，都根據(jù)問(wèn)題的大小建立。如果次數(shù)內(nèi)在容許偏差次數(shù)超過(guò)最大極限值以前達(dá)到了目標(biāo)值，我們就認(rèn)為保持了平衡21。對(duì)于我們的EOM問(wèn)題，我們?cè)O(shè)置次數(shù)內(nèi) 0.38*(3*m*n)和最大容許偏差= 0.6

23、2*(3*m*n)。我們說(shuō)取得了最后溫度，如果在那個(gè)溫度的馬而可夫鏈的整個(gè)軌跡里，最大和最小成本的差值等于在那個(gè)溫度的一次可接受轉(zhuǎn)換里的成本的最大一次變化。下列偽代碼程序描述了解決 EOM問(wèn)題的模擬退火過(guò)程(SAEOM)。解決EOM問(wèn)題的模擬退火過(guò)程(SAEOM)：Begin初始化()；k := 0；s := ；Repeat Until 平衡達(dá)到 doBegin 從N(s)產(chǎn)生； If () then s := Else If exp(f(s)-f()/t) > random0,1) then s := End；k := k+1；計(jì)算t； Until 停止準(zhǔn)則成立End與Kir

24、patrick16提出的模擬退火技巧相比，這個(gè)用Huang方法21的新SA技巧能通過(guò)退火過(guò)程動(dòng)態(tài)調(diào)節(jié)馬爾可夫鏈的長(zhǎng)度達(dá)到平衡，退火需要的CPU時(shí)間也大大地下降了。C.詳細(xì)規(guī)劃和準(zhǔn)確的成本估計(jì)在這一層，確定每個(gè)小區(qū)內(nèi)的基站位置，諸如天線塔高度，天線增益和發(fā)射功率等參數(shù)都進(jìn)一步根據(jù)每個(gè)小區(qū)的地形不規(guī)則性的特征，表面覆蓋和環(huán)境進(jìn)行調(diào)整。從上面兩層得到的結(jié)果已滿足了覆蓋性能，并試圖滿足話務(wù)要求。但不管怎樣，在某些小區(qū)的話務(wù)過(guò)載可能仍然存在。在這一層，可以用Hale6和Gamst23的信道分配策略來(lái)提供信道數(shù)的下界。把在7820中提到的固定和動(dòng)態(tài)信道分配策略應(yīng)用于蜂窩系統(tǒng)的網(wǎng)絡(luò)規(guī)劃以提供足夠的容量來(lái)為預(yù)

25、期的話務(wù)量服務(wù)，并保持無(wú)線干擾到最小限度。如果系統(tǒng)性能在調(diào)整后達(dá)到了要求，最后的系統(tǒng)設(shè)計(jì)就確定了，也就可以估計(jì)出蜂窩系統(tǒng)的成本。否則在這一層的結(jié)果將反饋到第一層和第二層。然后重復(fù)整個(gè)過(guò)程。在這種情況下，可能需要增加小區(qū)的數(shù)量以滿足規(guī)定的服務(wù)質(zhì)量。模擬結(jié)果A.HOP模型的應(yīng)用分層優(yōu)化方法被用來(lái)設(shè)計(jì)提供如圖1和圖3所示的為新加坡地區(qū)提供服務(wù)的蜂窩系統(tǒng)。在我們的研究中使用了模仿新加坡地形，話務(wù)分布和人口的數(shù)據(jù)。整個(gè)地區(qū)被分為三種類(lèi)型和100個(gè)網(wǎng)格。表1列出了關(guān)于每個(gè)網(wǎng)格的話務(wù)密度和地面類(lèi)型等信息。服務(wù)區(qū)域S有625km，每個(gè)網(wǎng)格的區(qū)域面積約為2.5*2.5 km。在系統(tǒng)設(shè)計(jì)中采用了7小區(qū)頻率復(fù)用模型

26、。假設(shè)要達(dá)到90%的區(qū)域覆蓋率并且忙時(shí)初始呼叫的阻塞率5。當(dāng)2.3時(shí)，相應(yīng)于90的區(qū)域覆蓋率，邊界處的位置覆蓋75，其中是接收信號(hào)的慢衰落部分的標(biāo)準(zhǔn)偏差，是距離因子的指數(shù)2。對(duì)于給定的位置覆蓋概率和要求的C/N和C/I，設(shè)置邊界處的接收信號(hào)強(qiáng)度93dbm19。假設(shè)每個(gè)小區(qū)的信道數(shù)為45，平均通話時(shí)長(zhǎng)為1.76min/call，呼叫嘗試率為0.9call/h，則每小區(qū)可提供的話務(wù)負(fù)載為39.6愛(ài)爾蘭，能為=(39.6*60)/(1.76*0.9)=1500subscribers/h的總移動(dòng)單元數(shù)提供服務(wù)。首先，開(kāi)始進(jìn)行設(shè)計(jì)時(shí)先需要確定小區(qū)數(shù)的上界。從(4)(6)我們可得17，d3.53km。從(

27、7)我們有29400/150020。同時(shí)考慮覆蓋和話務(wù)性能，我們選擇n = max(,) = 20。接著，來(lái)確定20個(gè)小區(qū)的安置，假設(shè)給出系統(tǒng)成本的標(biāo)準(zhǔn)化參數(shù)如下：=1000，=5.0，10.0，0.5?；竞鸵苿?dòng)單元的參數(shù)選擇如下9：對(duì)所有的小區(qū)k，。根據(jù)24和25，我們得到了天線成本和其增益及發(fā)射機(jī)(或接收機(jī))成本和其發(fā)射功率之間的逼近線性關(guān)系。假設(shè)給出關(guān)于天線增益g的成本函數(shù)如下： = 40+Ca·g M 關(guān)于發(fā)射功率P的成本函數(shù)如下： = 60 + Ct·P M 其中M是一個(gè)大的正數(shù)。我們根據(jù)上面的具體參數(shù)應(yīng)用模擬退火算法SAEOM來(lái)求解EOM問(wèn)題。冷卻進(jìn)度表的控制

28、參數(shù)如下：初始接受率0.9，次數(shù)內(nèi)目標(biāo)0.38*3*20*100，最大容許偏差= 0.62*(3*m*n)，最大生成極限4*MUB21。在HP-C180的UNIX系統(tǒng)上用C語(yǔ)言執(zhí)行了這個(gè)算法。圖3給出了一個(gè)初始可行解(初始設(shè)計(jì))。具有相同陰影的相鄰網(wǎng)格組成一個(gè)小區(qū)?？傁到y(tǒng)成本為24349.68。圖4給出了用SAEOM算法求出的最優(yōu)解。這個(gè)最優(yōu)解是在用不同的初始可行解運(yùn)行程序10次后才獲得的。最終設(shè)計(jì)fc(s)的鄰近最優(yōu)系統(tǒng)成本是20139.20。小區(qū)數(shù)進(jìn)一步減少了6個(gè)。圖5顯示了收斂記錄，即用SAEOM算法求解EOM問(wèn)題的退火曲線。退火需要的平均CPU時(shí)間為34.65分鐘。為了評(píng)估SA方法求得

29、的解，我們把它與用Aarts和Korst15的本地搜索過(guò)程求得的最佳解和用隨機(jī)生成過(guò)程獲得的解比較。用本地搜索過(guò)程求得的最佳解為系統(tǒng)成本fc(s)20452.4和小區(qū)數(shù)n13。如成本函數(shù)(19)所示，每個(gè)小區(qū)的固定成本決定總系統(tǒng)成本。這意味著成本有效設(shè)計(jì)應(yīng)該有較少的小區(qū)數(shù)和每個(gè)小區(qū)較高的平均話務(wù)負(fù)載。圖6和圖7分別表示用SAEON和本地搜索方法求得的最佳解中的話務(wù)量柱形圖。圖8表示在小區(qū)數(shù)也是13這種情況下，隨機(jī)生成過(guò)程獲得的解的話務(wù)量分布。虛線和實(shí)心條分別代表每個(gè)小區(qū)能提供的話務(wù)負(fù)載和需要的話務(wù)負(fù)載。從圖6-8，我們觀察到用SAEON求得的逼近最優(yōu)解在能提供的話務(wù)負(fù)載和需要的話務(wù)負(fù)載之間取得了好的折衷。與其它兩個(gè)過(guò)程相比，每個(gè)小區(qū)的話務(wù)負(fù)載也呈均勻分布。如圖4 的最終設(shè)計(jì)所示，這個(gè)設(shè)計(jì)能滿足覆蓋要求，同時(shí)也努力用最小的小區(qū)數(shù)和最佳的小區(qū)安置適應(yīng)非一致話務(wù)負(fù)載。天線增益和發(fā)射功率的逼近最優(yōu)值可從最佳解中獲得。在最后一步，基站和移動(dòng)單元的所有參數(shù)都要根據(jù)所在小區(qū)內(nèi)具體的地形數(shù)據(jù)和覆蓋特征進(jìn)行調(diào)整。從上面兩層獲得的結(jié)果能滿足覆蓋的質(zhì)量要求，但并不能提供每個(gè)小區(qū)的所有預(yù)期話務(wù)量。在最后一層，Gamst23技巧被用來(lái)確定要分配的信道數(shù)下界。然后進(jìn)一步