中繼站數(shù)目最優(yōu)化方案

PAGEPAGE13中繼站數(shù)目最優(yōu)化方案摘要現(xiàn)代社會(huì)，通信技術(shù)在每個(gè)人的生活中有這不可替代地位，可以說(shuō)沒(méi)有通信技術(shù)的發(fā)展就不會(huì)有我們今天便捷的生活。而中繼站是通信技術(shù)中的一貫重要環(huán)節(jié)，中繼站的布局合理性直接關(guān)系到通信的質(zhì)量，以及用戶對(duì)通信公司服務(wù)態(tài)度的滿意度。布局合理的中繼站，不僅可以提高通信質(zhì)量，還可以為企業(yè)節(jié)省很大一部分資金。合理布局網(wǎng)絡(luò)以提高服務(wù)質(zhì)量是無(wú)線網(wǎng)絡(luò)設(shè)計(jì)中的一個(gè)重要挑戰(zhàn)。問(wèn)題一：在一個(gè)半徑40英里的圓形區(qū)域里，用最少量的中繼站來(lái)容納1000同時(shí)并發(fā)用戶。把正多邊形無(wú)遺漏覆蓋原理當(dāng)中正六邊形的重疊面積最小應(yīng)用到模型中，從而得出：容納1000同時(shí)并發(fā)用戶的一個(gè)數(shù)學(xué)模型為：（R=40，r（）是中繼站的覆蓋半徑）可以，很快算出對(duì)應(yīng)覆蓋半徑中繼站需要的最小數(shù)量。問(wèn)題二：在一個(gè)半徑40英里的圓形區(qū)域里，用最少量的中繼站來(lái)容納10000同時(shí)并發(fā)用戶。一種方法就是在問(wèn)題一的模型上疊加5層，還有一種方法是類(lèi)比在圓中隨機(jī)畫(huà)直徑時(shí)，直徑與同心圓的交點(diǎn)密度與其半徑成反比的思想。假設(shè)在圓形區(qū)域內(nèi)布置中繼站密度也與其離中心的距離成反比。再由問(wèn)題一和網(wǎng)絡(luò)的層次為6設(shè)圓形區(qū)域邊界上的密度為（A是中繼站覆蓋圓的內(nèi)接正六邊形），可以建立模型為：（是點(diǎn)到圓形區(qū)域中心的距離）根據(jù)模型：可以，很快算出對(duì)應(yīng)覆蓋半徑中繼站需要的最小數(shù)量。問(wèn)題三：在考慮由于山區(qū)在信號(hào)傳播過(guò)程中的阻礙作用的基礎(chǔ)上，重新計(jì)算最小中繼站數(shù)。由于傳輸信號(hào)在山區(qū)傳輸會(huì)受到山峰的阻擋使其在傳播過(guò)程中衰減，從而影響服務(wù)半徑，使其服務(wù)半徑縮短。引進(jìn)信號(hào)干擾相關(guān)系數(shù)，使得實(shí)際覆蓋半徑為理論半徑的倍。從而使問(wèn)題轉(zhuǎn)化為問(wèn)題一，二。關(guān)鍵詞：中繼站多層蜂窩網(wǎng)絡(luò)蜂窩通訊技術(shù)正六邊形信號(hào)干擾相關(guān)系數(shù)目錄1. 問(wèn)題重述 12. 問(wèn)題分析 13. 模型假設(shè) 14. 符號(hào)說(shuō)明 15. 模型建立與求解 15.1問(wèn)題一：在平坦地域并發(fā)服務(wù)1000人，是中繼站的數(shù)目最小的優(yōu)化問(wèn)題 15.1.1蜂窩通訊技術(shù)中信號(hào)覆蓋選用正六邊形原因分析 15.1.2考慮信道數(shù)限制 15.1.3模型建立 15.2問(wèn)題二：在平坦地形并發(fā)服務(wù)10000人，使中繼站的用量最少的問(wèn)題 15.2.1模型假設(shè) 15.2.2基本的多層網(wǎng)絡(luò) 15.2.3改進(jìn)的多層網(wǎng)絡(luò) 15.3問(wèn)題三：在山區(qū)重新計(jì)算上述問(wèn)題的最優(yōu)解 15.3.1模型假設(shè) 15.3.2模型建立 16. 模型檢驗(yàn) 17. 進(jìn)一步討論 28. 模型評(píng)價(jià) 29. 參考文獻(xiàn) 210. 附錄 210.1附錄一：中繼站感知半徑與所需中繼站數(shù)量n存在關(guān)聯(lián)=f()的matlab程序 210.2附錄二：模型檢驗(yàn)中圖5和圖6的matlab程序 2問(wèn)題重述甚高頻無(wú)線電頻譜包含信號(hào)的發(fā)送和接受，這種限制可以被中繼站所克服。中繼站就是一部負(fù)責(zé)接收并轉(zhuǎn)發(fā)無(wú)線電信號(hào)的電臺(tái)。由于建筑物及地形等的遮擋，在地面上的兩個(gè)電臺(tái)之間的信號(hào)可能無(wú)法直接互相傳送到，但這兩個(gè)電臺(tái)卻都能夠和這個(gè)中繼臺(tái)很好地通聯(lián)，于是各個(gè)電臺(tái)就通過(guò)中繼臺(tái)的轉(zhuǎn)發(fā)覆蓋到更廣的通聯(lián)范圍，幫助小功率設(shè)備擴(kuò)大信號(hào)的目的。中繼臺(tái)的接收與發(fā)射半徑覆蓋面大，通過(guò)中繼臺(tái)的轉(zhuǎn)發(fā)，就可以解決普通電臺(tái)與電臺(tái)之間因距離而不能通聯(lián)的制約。本題要求用數(shù)學(xué)建模方法來(lái)研究以下三個(gè)問(wèn)題：?jiǎn)栴}一：在一個(gè)半徑40英里的圓形區(qū)域里，用最少量的中繼站來(lái)容納1000并發(fā)用戶。問(wèn)題二：在一個(gè)半徑40英里的圓形區(qū)域里，用最少量的中繼站來(lái)容納10000并發(fā)用戶。問(wèn)題三：在考慮由于山區(qū)在信號(hào)傳播過(guò)程中的阻礙作用的基礎(chǔ)上，重新計(jì)算最小中繼站數(shù)2.問(wèn)題分析由問(wèn)題可以得出，問(wèn)題是要我們解決在一個(gè)半徑為40英里圓形區(qū)域中用最少的中繼站同時(shí)服務(wù)一定的用戶量。1）根據(jù)實(shí)際，每個(gè)中繼站的服務(wù)覆蓋面積為半徑為一定值的圓。要用一系列小圓完全覆蓋一個(gè)大圓不可能沒(méi)有重疊區(qū)域。因此可以得出，要使中繼站最少就得使重疊面積最小。因此可以把圓轉(zhuǎn)化成正多邊形，問(wèn)題轉(zhuǎn)化使用最少的正多邊形完全覆蓋大圓。由初等幾何知識(shí)證明可知，用同一種正多邊形拼成一個(gè)平面只有正三角形，正方形，正六邊形三種，其中正六邊形的重疊損失最小。2）當(dāng)人數(shù)超過(guò)一種PL所能提供的總信道數(shù)時(shí)，就需要根據(jù)實(shí)際情況建立多層網(wǎng)絡(luò)。3）如果是在山區(qū)，中繼站信號(hào)覆蓋情況將會(huì)受到地形不同程度的影響。因?qū)嶋H地形情況復(fù)雜多變，可以近似進(jìn)行定量分析，并提出信號(hào)干擾相關(guān)系數(shù)，給出平均情況下的解決方案。3.模型假設(shè)1）問(wèn)題一和問(wèn)題二中的圓形區(qū)域地勢(shì)平坦，不考慮房屋等人工建筑的阻礙作用和大氣影響2）在中繼站覆蓋范圍內(nèi)，用戶信號(hào)都能被接受到3）每個(gè)中繼站各種性能完全相同4）頻譜范圍是145到148兆赫在中繼站中的發(fā)射機(jī)的頻率要么高于接收機(jī)頻率600千赫，要么低于接收機(jī)頻率600千赫5）有54個(gè)不同的PL可用6）兩個(gè)通信頻率之間至少應(yīng)相差頻偏1kHz4.符號(hào)說(shuō)明5.模型建立與求解5.1問(wèn)題一：在平坦地域并發(fā)服務(wù)1000人，是中繼站的數(shù)目最小的優(yōu)化問(wèn)題此部分我們借用蜂窩通訊技術(shù)，利用正六邊形覆蓋原理解決在半徑為40mile區(qū)域中，中繼站的數(shù)目最小化問(wèn)題。蜂窩通訊技術(shù)中信號(hào)覆蓋選用正六邊形原因分析在中繼站應(yīng)用中，對(duì)于某一信號(hào)覆蓋區(qū)域，如何做到“毫無(wú)遺漏”的覆蓋即是無(wú)漏洞覆蓋問(wèn)題。按照節(jié)點(diǎn)覆蓋的圓盤(pán)模型，這個(gè)問(wèn)題可抽象為：對(duì)于面積為A的圖形F如果用半徑為r的圓去覆蓋，如何拼接這些圓，至少需要多少個(gè)這樣的圓才能完全覆蓋圖形F?？梢栽O(shè)想，無(wú)論用多么小的半徑為r的圓對(duì)某一區(qū)域進(jìn)行覆蓋都不可能是無(wú)重復(fù)無(wú)漏洞覆蓋。問(wèn)題的解決只能退讓到用最少個(gè)數(shù)的正多邊形完成重復(fù)最小的無(wú)漏洞覆蓋，這個(gè)問(wèn)題的解有如下的定理。定理1：用半徑為r的圓，以它的內(nèi)接正六邊形對(duì)區(qū)域進(jìn)行覆蓋，可得到重復(fù)覆蓋最少的無(wú)漏洞覆蓋。證明：考慮用同種的正n邊形來(lái)覆蓋平面，在一個(gè)頂點(diǎn)周?chē)辛薽個(gè)正n邊形的角。由于這些角的和應(yīng)為360°，因此成立。可以解得三組解，如式：這證明了用一種正多邊形覆蓋平面區(qū)域，只存在如下3種情況：1）由正三角形覆蓋；2）由正四邊形覆蓋；3）由正六邊形覆蓋。用半徑相同的圓的內(nèi)接正邊形來(lái)覆蓋平面，則相鄰兩個(gè)圓的公共面積占一個(gè)圓面積的比例如式：則當(dāng)n取以上3種情況時(shí)分別為相鄰兩圓的公共覆蓋面積占圓面積的百分率越小，所需要的正多邊形個(gè)數(shù)則越少。因此正六邊形是使用最少個(gè)結(jié)點(diǎn)可以覆蓋最大面積的圖形。5.1.2考慮信道數(shù)限制因?yàn)樵谥欣^站中發(fā)射機(jī)的頻率要么高于接收機(jī)頻率600，要么低于接收機(jī)頻率600。微波通訊頻帶145-148MHz?？傻?[145MHZ，148MHZ]每個(gè)中繼站能夠容納的同時(shí)通訊信號(hào)的數(shù)量是有限的，而且相鄰的中繼站之間也可能存在信號(hào)干擾。為了避免干擾，以及容納更多的在線用戶，解決方案通常是為每個(gè)中繼站分配一個(gè)固定的“亞音”頻率，中繼站只響應(yīng)附加了該亞音頻率的通訊信號(hào)?？紤]通常的微波通訊頻帶145-148MHz，國(guó)際標(biāo)準(zhǔn)亞音頻率一共54個(gè)，從67-254Hz不等。若所有中繼站采用同一個(gè)亞音頻率。為了區(qū)別不同的信號(hào)，兩個(gè)通信頻率之間至少應(yīng)相差頻偏1kHz，則一共可容納的通訊數(shù)量為（）/f=（147.4-145.6）×/1=1800。18001000只需建立單層網(wǎng)絡(luò)就能滿足服務(wù)需求。5.1.3模型建立將整個(gè)圓形區(qū)域分劃成若干蜂窩狀的正六邊形小區(qū),每個(gè)小區(qū)為一個(gè)中繼站服務(wù)區(qū)的內(nèi)接正六邊形。將這些小區(qū)進(jìn)行標(biāo)號(hào)，稱(chēng)最中間的小區(qū)為第0圈，在它外圍的6個(gè)小區(qū)為第1圈，依次稱(chēng)第i圈外的小區(qū)為第i+1圈。且每一圈正六邊形的中心的連線都形成一個(gè)正六邊形。設(shè)最外圈為第n圈，第i圈(i>1)中共有6*i個(gè)小區(qū)。這一關(guān)系很容易從（圖一）蜂窩網(wǎng)絡(luò)的幾何特征歸納得出?？傻萌φ呅蔚膫€(gè)數(shù)NN=若使整個(gè)圓形區(qū)域被中繼站覆蓋，則中繼站無(wú)漏洞覆蓋區(qū)域面積大于整個(gè)圓形區(qū)域面積。圓形區(qū)域總面積為：設(shè)中繼站的覆蓋半徑為r，則ON=OM=ON為第n圈形成的正六邊形的頂點(diǎn)以O(shè)MR，估計(jì)正六邊形的圈數(shù)，即因?yàn)檎呅蔚拿織l不邊都等價(jià)，所以以這層的一條邊，即EF為研究對(duì)象。又因?yàn)镋F關(guān)于點(diǎn)M對(duì)稱(chēng)，所以從N點(diǎn)出發(fā)依次向M點(diǎn)考慮每一個(gè)中繼站是否在圓形區(qū)域內(nèi)，即（為從N起向M依次數(shù)過(guò)的正六邊形個(gè)數(shù)N為零）由蜂窩網(wǎng)絡(luò)的幾何特征歸納得出在n+1圈形成的正六邊形的一條邊上還需要補(bǔ)充的正六邊形數(shù)為由上述公式可得需要最小中繼站數(shù)為圖1蜂窩網(wǎng)絡(luò)覆蓋不失一般性，取r=3mile，用matlab編程計(jì)算可得（附錄1），此時(shí)共有253個(gè)中繼站。中繼站的數(shù)量很大程度上取決于中繼站的服務(wù)距離。如果采用較大靈敏的無(wú)線電傳感器或者采用更高的天線，則其服務(wù)距離也相應(yīng)增加。當(dāng)取=5miles時(shí)，中繼站數(shù)量為n=109。顯然中繼站感知半徑與所需中繼站數(shù)量n存在關(guān)聯(lián)=f()。統(tǒng)計(jì)得和n的數(shù)據(jù)如表1顯然中繼站感知半徑與所需中繼站數(shù)量n存在關(guān)聯(lián)=f()。利用以下程序計(jì)算的數(shù)據(jù)如表1：clearall,clcr=3:12R=40;n=floor(2.*R./3./r);d=(3/2).*r.*nt=ceil(n./2-sqrt(R*R-d.*d)./(sqrt(3).*r));forl=1:10sum=0;fors=1:n(l)sum=sum+6*s;endm(l)=-2.*t(l).*6+1+sum+6.*n(l);endm中繼站覆蓋半徑r(mile)3456789101112中繼站數(shù)n25315110973554331313119表15.2問(wèn)題二在平坦地形并發(fā)服務(wù)10000人，使中繼站的用量最少的問(wèn)題該問(wèn)題分別考慮信道數(shù)的基本多層網(wǎng)絡(luò)模型和考慮信道數(shù)的改進(jìn)的多層網(wǎng)絡(luò)模型情況的研究，在考慮信道數(shù)的基本多層網(wǎng)絡(luò)模型情況下時(shí)各層網(wǎng)絡(luò)互不干擾，只需在問(wèn)題一的基礎(chǔ)上疊加多層。在考慮信道數(shù)的改進(jìn)改進(jìn)的多層模型時(shí)引進(jìn)了概率統(tǒng)計(jì)理論，考慮在通信中的隨機(jī)性過(guò)程使模型更接近實(shí)際。5.2.1模型假設(shè)1）以圓形區(qū)域中心為圓心，厚度相等的圓環(huán)上的中繼站數(shù)目相等2）中繼站之間沒(méi)有干擾5.2.2基本的多層網(wǎng)絡(luò)因每一種PL的信道數(shù)為1800小于服務(wù)用戶10000人?？梢?jiàn)，要滿足10000名用戶的需求，必須設(shè)置多個(gè)亞音頻率，基于問(wèn)題一的解決方案，我們構(gòu)建出多層蜂窩網(wǎng)絡(luò)。用戶設(shè)備應(yīng)能夠自動(dòng)搜尋可用頻率，并可設(shè)定多檔亞音頻率。比如，某個(gè)亞音頻率的中繼站網(wǎng)絡(luò)層的1800個(gè)容量被全部占用時(shí)，后進(jìn)的用戶可將設(shè)備亞音頻率調(diào)整至另一個(gè)尚未被占用完的亞音頻率層。這樣，就要求整個(gè)系統(tǒng)的網(wǎng)絡(luò)層數(shù)能夠足夠多。明顯，最少的網(wǎng)絡(luò)層數(shù)10000/1800=6。即使用6個(gè)亞音頻率。因此可以設(shè)置6層蜂窩網(wǎng)絡(luò)。每一層的結(jié)構(gòu)與情況1的蜂窩網(wǎng)絡(luò)相同，且這6層網(wǎng)絡(luò)的結(jié)構(gòu)彼此相同。5.2.3改進(jìn)的多層網(wǎng)絡(luò)憑借現(xiàn)實(shí)生活中的經(jīng)驗(yàn)，在圓中心的小區(qū)，會(huì)安置更多的繼站，以滿足外圍相互通訊時(shí)對(duì)信道數(shù)量的要求。根據(jù)在圓中任意畫(huà)直徑在圓內(nèi)的小圓上的密度與其半徑成反比的實(shí)際情況：假設(shè)在多層網(wǎng)絡(luò)單位面積（）上中繼站的密度（為常數(shù)，為離圓形區(qū)域中心距離），且在邊緣上的密度為。（覆蓋面積為正六邊形的面積）可得不失一般性，取=3，可得=102.64=2579顯然中繼站感知半徑與所需中繼站數(shù)量n存在關(guān)聯(lián)=()。統(tǒng)計(jì)得和n的數(shù)據(jù)如表2中繼站覆蓋半徑r(mile)3456789101112中繼站數(shù)n25791451927645474363287233192162表2可見(jiàn)，當(dāng)用中繼站的服務(wù)半徑很大程度上影響著中繼站的數(shù)量。服務(wù)半徑越小需要的中繼站數(shù)量越大。因此，盡量用服務(wù)半徑比較大的中繼站，這樣能夠最大限度地減少中繼站數(shù)量。5.3問(wèn)題三在山區(qū)重新計(jì)算上述問(wèn)題的最優(yōu)解由于傳輸信號(hào)在山區(qū)傳輸會(huì)受到山峰的阻擋使其在傳播過(guò)程中衰減，從而影響服務(wù)半徑，使其服務(wù)半徑縮短。由于在實(shí)際中山區(qū)地形復(fù)雜多變，難以捉摸。所以采取簡(jiǎn)化取平均的方法，使模型能夠在有限的時(shí)間和資源條件下求解。5.3.1模型假設(shè)1）在山區(qū)，所有中繼站都建在山頂上2）信號(hào)在山區(qū)傳播只考慮出現(xiàn)下圖三種情況，且每種情況出現(xiàn)的概率相等3）忽略由于山高所影起的傳播損失圖2圖3圖注：（左邊三角形為山，中繼站在山頂，右邊為接受裝置）5.3.2模型建立在電磁理論中，越過(guò)障礙物的電波相對(duì)場(chǎng)強(qiáng)E/E0及地形損耗L可分別表示為：（）（1）L=20logFL≤0（2）E0是電波在自由空間傳播的場(chǎng)強(qiáng)，F(xiàn)是繞射系數(shù)是反射波（圖3）或繞射波（圖4）相對(duì)于直射波路徑而言的相位差。（）（3）（4）其中C和S是菲涅耳積分：（5）（6）V是無(wú)量綱參量：（7）是電波波長(zhǎng)，h、γ1和γ2的含義見(jiàn)圖3，4。圖4中h為負(fù)，根據(jù)式（7），則V為正。圖3中h為正，則V為負(fù)。鑒于山峰對(duì)信號(hào)的損耗作用，可知山區(qū)會(huì)影響中繼站信號(hào)傳播，直接影響中繼站覆蓋半徑，設(shè)山峰影響系數(shù)為，則在山區(qū)中繼站的信號(hào)覆蓋半徑為：Rm=*r當(dāng)用戶數(shù)小于1800時(shí)模型轉(zhuǎn)化為問(wèn)題一的求解以=0.5，為例Rm=0.5*r=1.5求得，=973表3給出了各種服務(wù)半徑及不同衰減系數(shù)的情況下所需要的最少中繼站數(shù)（計(jì)算程序附表二）34567891011120．84032411511098573554331310．6679403253187139109857361550．597357736725319915112110985730．41543865577403301241187151127109表3當(dāng)用戶人數(shù)大于1800時(shí)模型轉(zhuǎn)化為問(wèn)題二的求解。6.模型檢驗(yàn)本模型只考慮了在圓形區(qū)域中心放置中繼站的情況下使中繼站的數(shù)量最少的問(wèn)題，即特殊情況下的最優(yōu)解。而沒(méi)有考慮當(dāng)圓形區(qū)域中心和繼站不重疊的情況下使中繼站的數(shù)量最少的最優(yōu)解問(wèn)題。圖5，圖6為matlab模擬（附錄2）中心有中繼站的情況下的圖形。當(dāng)r相對(duì)R比較小時(shí)模擬結(jié)果與計(jì)算結(jié)果完全相同，但當(dāng)r大到R的0.2倍時(shí)模擬結(jié)果與計(jì)算結(jié)果出現(xiàn)差6誤差（如圖6）。圖5