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

摘要：本論文涉及蜂窩移動(dòng)通信系統(tǒng)的設(shè)計(jì)優(yōu)化和無線網(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)性能。我們把問題闡述為一個(gè)大型的組合優(yōu)化模型，通過此模型確定小區(qū)的最優(yōu)數(shù)量并選擇最佳的基站位置。模擬退火方法被用來解決這個(gè)困難的組合問題。模擬結(jié)果證明了HOP方法在無線網(wǎng)絡(luò)規(guī)劃中的可行性和有效性。

關(guān)鍵詞：蜂窩移動(dòng)通信系統(tǒng)，最優(yōu)化，無線網(wǎng)絡(luò)規(guī)劃，模擬退火

Ⅰ介紹

隨著對(duì)移動(dòng)通信業(yè)務(wù)需求的巨大增長(zhǎng)，系統(tǒng)設(shè)計(jì)優(yōu)化和無線網(wǎng)絡(luò)規(guī)劃的問題變得越來越重要。雖然在移動(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)境來確定�；�站和移動(dòng)單元的設(shè)計(jì)參數(shù)必須要等到小區(qū)的部署全部完成后才能具體化。最后，在話務(wù)和避免干擾等方面能改善系統(tǒng)性能的信道分配[6]-[8]只有在移動(dòng)蜂窩網(wǎng)絡(luò)的結(jié)構(gòu)被詳細(xì)說明后才能決定。

在決定任何通信系統(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ī)劃中都沒有直接包括金融上的規(guī)劃或者考慮成本。另一方面，如Analysis STEM建模系統(tǒng)等的一些軟件是決策支持工具以獲得金融模型并提供蜂窩移動(dòng)系統(tǒng)的成本分析。但在它們的成本模型中又沒有考慮網(wǎng)絡(luò)規(guī)劃。這篇論文試圖同時(shí)考慮成本和網(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ī)劃模型通常不能被公式化或無法求解。在本論文中，我們描述了關(guān)于移動(dòng)蜂窩通信系統(tǒng)設(shè)計(jì)的網(wǎng)絡(luò)規(guī)劃的分層特性，提出了一個(gè)分層優(yōu)化規(guī)劃方法(HOP)以確定無線網(wǎng)絡(luò)的結(jié)構(gòu)，即小區(qū)的數(shù)量，小區(qū)的大小，小區(qū)的安置，天線增益及天線高度的參數(shù)和基站及移動(dòng)單元的發(fā)射功率。一個(gè)組合優(yōu)化模型被推導(dǎo)出來以確定小區(qū)的最佳數(shù)量和基站的最佳位置使得在總的系統(tǒng)成本最小化的同時(shí)又能保證良好的覆蓋質(zhì)量和話務(wù)性能。

規(guī)劃模型是一個(gè)有難度的組合優(yōu)化問題[13]。諸如分支界限法和動(dòng)態(tài)規(guī)劃法之類的優(yōu)化算法不能在合理的時(shí)間內(nèi)求得優(yōu)化解[13]。因?yàn)闋可娴胶芏嘧兞亢蛷?fù)雜的約束，被用來解決大型組合優(yōu)化問題的分解法和拉格朗日松馳法[14]可能也無法應(yīng)用到規(guī)劃模型中。在本論文中，一個(gè)建立在模擬退火(SA)基礎(chǔ)上的算法被推導(dǎo)出來用于解決此問題，并在合理的計(jì)算量?jī)?nèi)求得了逼近的最優(yōu)結(jié)果。

本論文的安排如下。在第二節(jié)，我們描述了蜂窩無線網(wǎng)絡(luò)規(guī)劃問題。第三節(jié)提出了解決這個(gè)問題的分層優(yōu)化規(guī)劃方法。在這一節(jié)還提出了組合優(yōu)化模型和模擬退火算法。最后，在第四節(jié)給出了用HOP方法實(shí)現(xiàn)新加坡的蜂窩移動(dòng)通信服務(wù)系統(tǒng)的網(wǎng)絡(luò)規(guī)劃的模擬結(jié)果。

Ⅱ問題陳訴

如圖1所示，假如我們想要發(fā)展一個(gè)蜂窩移動(dòng)通信系統(tǒng)為新加坡地區(qū)提供服務(wù)。整個(gè)地區(qū)將覆蓋三種類型的土地：市區(qū)，郊區(qū)和農(nóng)村。我們需要考慮非一致的話務(wù)分布：話務(wù)高峰通常在市中心，局部話務(wù)高峰在郊區(qū)中心。給定與覆蓋性能相關(guān)的地區(qū)覆蓋概率 。邊界處的定位概率 和覆蓋邊界處接收信號(hào)強(qiáng)度的門限電平 可以從覆蓋概率 和要求的信號(hào)強(qiáng)度，即載干比C/N[2]中推導(dǎo)得出。服務(wù)等級(jí)被設(shè)定為在忙時(shí)發(fā)起呼叫的阻塞概率 。為滿足業(yè)務(wù)要求在系統(tǒng)中采用了頻率復(fù)用方案。

問題是怎樣設(shè)計(jì)一個(gè)最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)，即確定小區(qū)的數(shù)量，小區(qū)的大小，每個(gè)基站的位置和基站及移動(dòng)單元的參數(shù)，以保證達(dá)到要求的性能目標(biāo)，并使總的系統(tǒng)成本最小化。基站設(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ī)劃活動(dòng)包括：性能的說明和分析，從小區(qū)的數(shù)量及小區(qū)的位置方面來說的形式上的小區(qū)規(guī)劃，和關(guān)于射頻小區(qū)參數(shù)的設(shè)置及信道分配的詳細(xì)小區(qū)設(shè)計(jì)。

Ⅲ網(wǎng)絡(luò)規(guī)劃和設(shè)計(jì)方法

我們提出了蜂窩移動(dòng)通信網(wǎng)絡(luò)設(shè)計(jì)的三層HOP方法。

在第一層，決定了小區(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ù)密度和不同類型服務(wù)區(qū)域的地形特征。如圖1 所示，整個(gè)區(qū)域被劃分為市區(qū)，郊區(qū)和農(nóng)村。這些區(qū)域進(jìn)一步被劃分為更小的網(wǎng)格。環(huán)境結(jié)構(gòu)方面的信息，用戶密度和每個(gè)網(wǎng)格的平均俯角等都可以從地理信息系統(tǒng)(GIS)的數(shù)據(jù)庫(kù)里得到。

詳細(xì)規(guī)劃在第三層進(jìn)行，每個(gè)小區(qū)的具體參數(shù)，如天線模型及其增益，發(fā)射功率，天線高度和信道利用率等都在這一層設(shè)置。最后，把成本估計(jì)出來。

規(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)村等地形是準(zhǔn)光滑或不規(guī)則的不同環(huán)境下無線傳播的特性。在蜂窩系統(tǒng)的設(shè)計(jì)中這個(gè)模型廣泛應(yīng)用于預(yù)測(cè)不同環(huán)境下的路徑損失[17][19]。

關(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，且頻率f≥400MHz。

郊區(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è)計(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)車輛的交通流量來預(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)度的門限電平。
    射頻輸出的峰值功率(dbW)。
    發(fā)射天線的輸入功率(dbW)。
    接收天線的接收功率(dbW)。
, 分別為基站和移動(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)椋?/p>

L(d) = 123.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ù)量的分布情況來確定覆蓋區(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ū)位置和小區(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ū)由相鄰的具有相同分類的幾個(gè)網(wǎng)格組成。在本論文中，建立了一個(gè)組合優(yōu)化模型來確定那個(gè)網(wǎng)格屬于那個(gè)小區(qū)和基站參數(shù)的最優(yōu)值。我們考慮關(guān)于覆蓋標(biāo)準(zhǔn)的“硬”約束和非一致話務(wù)需求的“軟”約束，“軟”約束可被放松且可通過補(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è)問題，我們引入以下決策變量：
=   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é)約一個(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)的上界和下界。
  分別為小區(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)   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)用來確保覆蓋性能。約束(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)傳播損耗 通過Hata預(yù)測(cè)模型進(jìn)行計(jì)算。根據(jù)以下條件[1],[9]： = 10W， =30m， =3m， =12dBi， = 2dBi，l = 4dB，f = 900MHz，我們有：

＝ а＋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)化問題，因?yàn)樵谀Ｐ椭杏泻芏嘧兞亢蛷?fù)雜的約束[13]。沒有一種優(yōu)化算法能在合理的時(shí)間里求得最優(yōu)解。在文獻(xiàn)[15]和[16]中報(bào)導(dǎo)的建立在模擬退火(SA)基礎(chǔ)上的算法被用來解決這個(gè)問題，并在合理的時(shí)間內(nèi)求得了逼近最優(yōu)解。

對(duì)于求解NP完全組合問題的逼近解來說模擬退火是種好方法[13]。它已被成功應(yīng)用于某些領(lǐng)域，如計(jì)算機(jī)的優(yōu)化設(shè)計(jì)[16]，圖象處理，信道分配[8][20]和規(guī)劃布局問題。算法采用一種迭代方案，它模擬物理退火過程：加熱固體直到其融化，然后花最少的能量冷卻它使其結(jié)晶至基態(tài)。

為了用模擬退火過程解決EOM問題，需要考慮下面四個(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ù)兩者的要求，沒有幾個(gè)可行解可被求得。因而引入話務(wù)約束(14)到目標(biāo)函數(shù)，目標(biāo)函數(shù)就從(12)變?yōu)樽钚』�基站的總設(shè)備成本和破壞話務(wù)負(fù)載后引起的總補(bǔ)償，即：
      (22)
其中函數(shù)[x] =max(0,x)。

因?yàn)?12)中的系統(tǒng)固定成本 不影響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 以確保可接受轉(zhuǎn)換與提議轉(zhuǎn)換之比的特定接受率χ接近1[15]。這可以通過從一個(gè)小的正數(shù)t 出發(fā)，迭代地變換它直到達(dá)到接受率χ來得到。

Huang[21]用在某一溫度的成本分布的標(biāo)準(zhǔn)偏差來決定下個(gè)溫度的減小量，并提出下面的溫度遞減規(guī)則：
                (23)
其中 是在溫度t 的成本分布的標(biāo)準(zhǔn)偏差； 是發(fā)生在兩個(gè)連續(xù)溫度t 和t 之間的平均成本的減少量。為保持準(zhǔn)平衡，當(dāng) 。 的典型值0.7。

在某個(gè)溫度平衡意味著齊次馬爾可夫鏈的固定成本分布的建立。Huang假設(shè)了一個(gè)關(guān)于平衡的成本的正態(tài)分布，它們的平均值 和標(biāo)準(zhǔn)偏差 都由馬爾可夫鏈估計(jì)而來。他們提出了完成固定分布檢查的平衡條件：一旦平衡建立，其成本限制在范圍 內(nèi)可接受的轉(zhuǎn)換次數(shù)的比率將達(dá)到一個(gè)穩(wěn)定值μ＝erf( )，其中 介于平均成本 (它被稱為次數(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ù)問題的大小建立。如果次數(shù)內(nèi)在容許偏差次數(shù)超過最大極限值以前達(dá)到了目標(biāo)值，我們就認(rèn)為保持了平衡[21]。

對(duì)于我們的EOM問題，我們?cè)O(shè)置次數(shù)內(nèi) ＝0.38*(3*m*n)和最大容許偏差=   0.62*(3*m*n)。

我們說取得了最后溫度，如果在那個(gè)溫度的馬而可夫鏈的整個(gè)軌跡里，最大和最小成本的差值等于在那個(gè)溫度的一次可接受轉(zhuǎn)換里的成本的最大一次變化。

下列偽代碼程序描述了解決 EOM問題的模擬退火過程(SAEOM)。

解決EOM問題的模擬退火過程(SAEOM)：
Begin
初始化( )；
k := 0；
s := ；
Repeat
  Until 平衡達(dá)到 do
  Begin
    從N(s)產(chǎn)生 ；
    If ( ) then s :=
    Else
    If exp((f(s)-f( ))/t ) > random[0,1)   then s :=
  End；
  k := k+1；
  計(jì)算t ；
Until 停止準(zhǔn)則成立
End
與Kirpatrick[16]提出的模擬退火技巧相比，這個(gè)用Huang方法[21]的新SA技巧能通過退火過程動(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ù)過載可能仍然存在。在這一層，可以用Hale[6]和Gamst[23]的信道分配策略來提供信道數(shù)的下界。把在[7][8][20]中提到的固定和動(dòng)態(tài)信道分配策略應(yīng)用于蜂窩系統(tǒng)的網(wǎng)絡(luò)規(guī)劃以提供足夠的容量來為預(yù)期的話務(wù)量服務(wù)，并保持無線干擾到最小限度。

如果系統(tǒng)性能在調(diào)整后達(dá)到了要求，最后的系統(tǒng)設(shè)計(jì)就確定了，也就可以估計(jì)出蜂窩系統(tǒng)的成本。否則在這一層的結(jié)果將反饋到第一層和第二層。然后重復(fù)整個(gè)過程。在這種情況下，可能需要增加小區(qū)的數(shù)量以滿足規(guī)定的服務(wù)質(zhì)量。

Ⅳ模擬結(jié)果

A.HOP模型的應(yīng)用

分層優(yōu)化方法被用來設(shè)計(jì)提供如圖1和圖3所示的為新加坡地區(qū)提供服務(wù)的蜂窩系統(tǒng)。在我們的研究中使用了模仿新加坡地形，話務(wù)分布和人口的數(shù)據(jù)。整個(gè)地區(qū)被分為三種類型和100個(gè)網(wǎng)格。表1列出了關(guān)于每個(gè)網(wǎng)格的話務(wù)密度和地面類型等信息。服務(wù)區(qū)域S有625km ，每個(gè)網(wǎng)格的區(qū)域面積約為2.5*2.5 km 。在系統(tǒng)設(shè)計(jì)中采用了7小區(qū)頻率復(fù)用模型。假設(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)度 ＝－93dbm[1][9]。假設(shè)每個(gè)小區(qū)的信道數(shù)為45，平均通話時(shí)長(zhǎng)為1.76min/call，呼叫嘗試率為0.9call/h，則每小區(qū)可提供的話務(wù)負(fù)載為39.6愛爾蘭，能為 =(39.6*60)/(1.76*0.9)=1500subscribers/h的總移動(dòng)單元數(shù)提供服務(wù)。

首先，開始進(jìn)行設(shè)計(jì)時(shí)先需要確定小區(qū)數(shù)的上界。從(4)－(6)我們可得 ＝17，d ＝3.53km。從(7)我們有 ＝29400/1500 20。同時(shí)考慮覆蓋和話務(wù)性能，我們選擇n = max( , ) = 20。

接著，來確定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來求解EOM問題。冷卻進(jìn)度表的控制參數(shù)如下：初始接受率χ＝0.9，次數(shù)內(nèi)目標(biāo)＝0.38*3*20*100，最大容許偏差= 0.62*(3*m*n)，最大生成極限＝4*MUB[21]。在HP-C180的UNIX系統(tǒng)上用C語言執(zhí)行了這個(gè)算法。

具有相同陰影的相鄰網(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問題的退火曲線。退火需要的平均CPU時(shí)間為34.65分鐘。

為了評(píng)估SA方法求得的解，我們把它與用Aarts和Korst[15]的本地搜索過程求得的最佳解和用隨機(jī)生成過程獲得的解比較。用本地搜索過程求得的最佳解為系統(tǒng)成本fc(s)＝20452.4和小區(qū)數(shù)n＝13。如成本函數(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ī)生成過程獲得的解的話務(wù)量分布。虛線和實(shí)心條分別代表每個(gè)小區(qū)能提供的話務(wù)負(fù)載和需要的話務(wù)負(fù)載。從圖6-8，我們觀察到用SAEON求得的逼近最優(yōu)解在能提供的話務(wù)負(fù)載和需要的話務(wù)負(fù)載之間取得了好的折衷。與其它兩個(gè)過程相比，每個(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ù)量。在最后一層，Gamst[23]技巧被用來確定要分配的信道數(shù)下界。然后進(jìn)一步應(yīng)用Dugue-anton[20]的信道分配過程去滿足話務(wù)要求和避免干擾。

B.SA算法的性能

模擬退火方法SAEOM的性能研究分兩個(gè)方面：解的質(zhì)量和執(zhí)行時(shí)間[13]。我們把SAEOM求得的次優(yōu)解比作用本地搜索方法及隨機(jī)生成過程獲得的最優(yōu)解。如表Ⅱ和Ⅲ所示的四種不同大小的問題都應(yīng)用了這些方法。

本地搜索算法是一種由Aarts[15]提出的貪婪算法，用本地搜索算法求得的解嚴(yán)重地依賴于初始解。計(jì)算時(shí)間的上界，即最差情況下的時(shí)間復(fù)雜度對(duì)很多問題而言都不可知[15][13]。給定次數(shù)N 對(duì)相同的問題用不同的初始值運(yùn)行本地搜索算法,我們就得到了平均時(shí)間，平均CPU時(shí)間，最佳結(jié)果及進(jìn)行大量?jī)?yōu)化獲得最佳結(jié)果所花的總CPU時(shí)間[15][8]。

在對(duì)同樣的問題運(yùn)行SAEOM10次后就得到了模擬退火算法SAEOM的CPU時(shí)間和最佳結(jié)果的平均值。

從中可注意到模擬退火方法能在較短的時(shí)間內(nèi)求得較好的解。由于固定小區(qū)成本 決定總系統(tǒng)成本，如表Ⅱ所示在SAEOM的平均結(jié)果和本地搜索的最佳結(jié)果之間沒有發(fā)現(xiàn)什么顯著區(qū)別。當(dāng)話務(wù)成本因子 增加時(shí)，與表Ⅱ相比，表Ⅲ中的SAEOM的解和本地搜索的解的差別變大。從表Ⅱ和Ⅲ可以看出，每次執(zhí)行本地搜索所需的CPU時(shí)間遠(yuǎn)遠(yuǎn)小于模擬退火所需的CPU時(shí)間。但與模擬退火相比，本地搜索需要多得多的時(shí)間去得到最優(yōu)解。

一般情況下模擬退火算法解的質(zhì)量可以通過調(diào)節(jié)控制參數(shù)(λ,χ,etc)的值，減慢冷卻過程和增加馬爾可夫鏈的長(zhǎng)度[15]來得到改善。圖9顯示了應(yīng)用SAEOM算法時(shí)，解的質(zhì)量和運(yùn)行時(shí)間之間的折衷。成本為 的最終解的質(zhì)量由如下定義的相當(dāng)誤差ε決定：
      ε=
其中 是曾經(jīng)求得的最佳值。對(duì)于大型案例的廣泛研究表明一個(gè)具有良好質(zhì)量的解能通過降低λ和增加χ來得到。

Ⅴ結(jié)論

本論文研究了對(duì)于蜂窩移動(dòng)通信網(wǎng)絡(luò)規(guī)劃的經(jīng)濟(jì)優(yōu)化建模問題。提出了一個(gè)分層優(yōu)化規(guī)劃方法，它既考慮到覆蓋的要求又考慮到話務(wù)負(fù)載。發(fā)展了一個(gè)組合優(yōu)化模型去確定合適的小區(qū)數(shù)量和選擇最佳的基站位置。一個(gè)建立在改進(jìn)的模擬退火基礎(chǔ)上的算法被用來求解這個(gè)模型并取得了逼近最優(yōu)解。大型的復(fù)雜移動(dòng)通信系統(tǒng)的資源管理和網(wǎng)絡(luò)規(guī)劃的最優(yōu)化技術(shù)的發(fā)展和應(yīng)用將是我們未來的研究課題。