G移動通信網絡基站建設方案分析目錄29837摘要 I31447第1章緒論 1243291.1研究背景和研究目的 1231851.2國內外研究進展 1318851.2.1關于基站選址優化的研究 1291951.2.2關于獅群算法的研究 2296101.3論文的結構安排 211059第2章通信基站的技術和優化算法 4264582.1移動通信技術 47232.2智能優化算法 46156第3章獅群算法及其優化 6233353.1獅群算法的簡介 672793.2獅群算法的具體求解方法 6163843.3對獅群算法的改進 8188213.3.1基站分散法 843473.3.2具體的算法： 83188第4章基于獅群算法的基站選址 11273024.1關于數據的基本的說明 11193714.2算法的基本流程 11116474.3運算的結果與分析： 12210704.4針對其他人口分布的測試： 14148944.5單純的基站分散 1682144.6PSO+基站分散： 1729815第5章結論 192300參考文獻 20第1章緒論1.1研究背景和研究目的移動通信技術在當今的生活中不可或缺。隨著科技的不斷進步，接入網絡的設備數量不斷增多，對于網絡的要求也不斷提高。基站位置部署直接影響網絡的質量。現實生活情況復雜，往往要同時考慮成本、覆蓋率、實際的地形等等情況。而需要部署的基站數量眾多，由人手工進行一一規劃的話，往往過于復雜。在實驗的準備階段發現，獅群算法具有快速收斂、需要調整的參數少、不易陷入局部最優解等特點。獅群算法通過記錄下歷史的最優解，在不斷的學習中發現更加優異的結果。這種不斷迭代尋求最優解的想法，使得其與普通的隨機探索有了天與地的差別，隨著迭代次數不斷增加，獅群算法發現更優解的可能性也越大。運用獅群算法在解決基站選址這一問題上有著非常重要的應用意義。本論文使用獅群算法來對基站選址這一課題進行探究。針對研究中所發現的問題，本文對獅群算法提出了優化的想法，提出“基站分散”的方法，縮短了程序的運算時間，提升了基站選址的效果。對于后續進行基站選址相關研究的研究人員來說，可能有一定參考作用。1.2國內外研究進展1.2.1關于基站選址優化的研究基站的選址對于通信運營商來說，是相當重要的課題。基站選址中所需要考慮的問題眾多，如人口分布、地形分布等等。現在關于基站選址所進行的研究眾多，研究的方向也各有差別。馬寶羅針對TD-LTE網絡的選址規劃問題，將免疫算法和粒子群算法進行了結合，提出了新穎的免疫粒子群算法的求解方案[1]。朱思峰針對TD-SCDMA網絡基站選址問題，利用免疫計算，提出了TD-SCDM的解決方案，并同時針對WCDMA、EEE802.16j等基站選址的問題展開了分析和討論[2]。謝許凱結合了遺傳算法和免疫算法來求解5G通信基站選址，并考慮到了基站建設成本、信號覆蓋范圍、網絡容量等因素[3]。劉家欣設計了針對5G基站的優化模型，并提出了帶權極小理想點法這一想法[4]。唐麗晴針對傳統優化算法容易陷入局部最優，而且收斂速度不夠滿意等問題，提出了鯨魚優化改進算法[5]。梁雪怡針對4G異構網絡基站選址問題和車聯網路側單元選址問題，提出了分區域和局部搜索機制添加到傳統算法的方案[6]。張凌志深入分析了網絡覆蓋的內在成因[7]。1.2.2關于獅群算法的研究獅群算法作為近幾年提出的優化算法，受到了很多人的矚目。關于獅群算法算進行的改進研究也相當眾多。李文陽探究了給予遺傳進化過程的獅群進化算法和基于捕獵合作機制的獅群優化算法，提出了模糊聚類和差分獅群進化算法[8]。戴子翔對獅群算法的更新策略進行改進，并將其應用于金融市場的分析[9]。劉振針對獅群算法收斂，容易陷入局部最優的缺點，提出了一種增強了局部搜索能力的獅群算法[10]。楊艷將獅群算法位置進行離散化，提出了貪心二進制獅群算法，以求解多維背包問題[11]。茍平章針對DV-Hop在三維空間中的定位誤差問題，利用獅群算法優化了三維定位算法[12]。郭穎針對獅群算法已陷入局部最優解的問題，提出了基于多Agent結構的獅群算法，運用不同的機制與方法改進了獅群算法的局部搜索能力[13]。張瓊藝將人工免疫機制中的濃度選擇方法導入獅群算法中，形成改進獅群算法，并將其應用于配電網的綜合優化[14]。劉東提出了雙目標獅群算法，并將其用于水庫的長期目標優化調度[15]。李曉東將遺傳算法的交叉、變異環節引入到獅群算法，增強了全局搜索能力[16]。1.3論文的結構安排為了解決通信選址這一問題，本文采用獅群算法進行了實驗。在傳統的獅群算法的基礎上，本文提出了“基站分散”的想法，提高了探索的速度和效果。并考慮到人口密度的影響，以盡可能接近實際的工程問題，提供高效的解決方案。本文的章節安排如下：第一章緒論部分，首先介紹本文的研究背景，分析目前基站選址問題的研究進展。第二章介紹了關于通信基站技術的進步和相關的智能算法。第三章介紹了獅群算法的基本內容。然后解釋了本文所提出的“基站分散”的想法。第四章使用獅群算法對基站選址進行了優化。對參數的最佳配置進行了探究。并探究了不同人口分布下的基站選址的結果。將獅群算法+“基站分散”、獅群算法、單純的“基站分散”三者進行了對比，探究算法的優劣。最后將“基站分散”和粒子群算法PSO進行了結合，探究“基站分散”在其他優化算法上的適應度。第五章結論。總結全文，探究進一步的研究方向。第2章通信基站的技術和優化算法2.1移動通信技術移動通信技術近年來的發展可以說的上是日新月異。上世紀80年代開始，通信技術已經迅速更新換代，現在的5G已經投入了商業應用。下面對這幾代移動通信技術進行簡單介紹。第一代通信技術（1G）誕生于二十世紀八十年代，主要采用模擬技術和頻分多址技術。現在正被逐步淘汰。第二代通信技術（2G）GSM是最廣泛采用的移動通信制式。以數字語音傳輸技術為核心，相比第一代，保密性能有不小改善。傳輸速度大概在10kbps,無法直接傳送電子郵件，軟件等。第三代通信技術（3G）采用智能信號處理技術。可以提供語音和多媒體數據通信。用戶的通信速度更加快速。第四代通信技術（4G）將WLAN技術與3G進行了融合，加快了圖像，數據，視頻的傳輸的速度，能達到100Mbps的下載速度，滿足絕大多數用戶對網絡的需求。第五代通信技術（5G）是最近提出來的通信技術，在通信速度上有著前面技術所不能比擬的優勢。但是由于5G基站的覆蓋范圍比較小，為了普及5G，大量基站的建設將會是不可或缺的。2.2智能優化算法智能優化算法是現在開發出來的用于解決最優化問題的比較新穎的算法。現在關于智能優化算法,有眾多研究。代表性的算法有梯度下降法，遺傳算法，PSO（粒子群算法），蟻群算法等。梯度下降法，也被稱為最陡下降法，在神經網絡中有著廣泛的應用。其想法是如果找到個局部最小值，那么函數上當前點對應梯度的反方向，進行迭代探索。遺傳算法是一種模擬自然進化的算法。它將問題的求解類比成生物進化中的基因的交叉，變異。現在已經在組合優化，人工生命等領域有著廣泛應用。粒子群算法（PSO）模擬鳥群的捕食行為。算法記錄下每一個粒子的個體最優解和整個粒子群的最優解，通過個體最優解、群體最優解和個體的運動慣性來確定每一個粒子的下一步探索。蟻群算法的思想來自于自然界中螞蟻尋找路徑的方式。在所經過的路徑，螞蟻會留下一種被稱為‘信息素’的物質。而螞蟻會選擇‘信息素’濃度高的路徑。這樣的結果是，最短的路徑（最優的解）所需時間短，通過的螞蟻數量多，而留下的信息素會吸引更多的螞蟻。通過這種正反饋，蟻群最后會全部沿著最短的路徑。第3章獅群算法及其優化3.1獅群算法的簡介根據觀察獅群協作捕獵的行為，抽象出了獅群算法。算法中定義了獅王，母獅，幼獅三種類型的獅子，每種獅子都有獨自的位置更新方式，并且遵循優勝劣汰的自然界的法則。獅群算法收斂的速度快，擁有較為優秀的全局尋優性，準確度較好，容易獲得較好的全局最優解。獅王是獅群中最強壯的公獅,是根據優勝劣汰所選擇出來的頭領，在保護自己的領土的同時不斷增強自己的實力。常還要不斷面對外來挑戰，例如狼群和流浪的雄獅。母獅通常需要捕獵，主要負責撫養幼獅。母獅按照從廣到密的搜索范圍進行搜索。一開始先廣撒網，大范圍偵察，之后將縮小行動范圍，對獵物周圍進行細致地搜索。在此過程中，它們不斷交換位置和獵物信息以提高效率。幼獅主要追隨成年獅子。年幼的時候，幼獅將會在獅王附近活動，或者接近母獅，學習生存技巧。而當長大后，幼獅則會離開獅群，獨自生存。成長后的幼獅幼獅會返回獅群，向獅王發起挑戰。獅群優化算法的主要思想如下所示:在待尋優空間中，給包括一定數量獅子的獅群分配一個初始的位置。最優秀的位置將會被分配給獅王。獅群中將會存在一定比例的成年獅，他們的任務是負責追捕獵物，獲取食物。獅王的位置將會在追捕獵物中不斷變化，一直占據著最為優秀的位置。幼獅在年幼的時候，待在母獅或者獅王周圍生活,成年后將被從獅群中驅逐出去。為了生存,離開獅群的幼獅會靠近自己曾經去過的最為優秀的位置。獅群算法通過這樣的模擬自然的方法，依靠著獅群的互相影響與合作，最終尋找到最為優秀的解。[17]3.2獅群算法的具體求解方法設定LSO參數中的問題維度為D，設定獅子數量為N，其中成年獅子的數量為nLeader，滿足：設定獅群中成年獅子（捕獵獅子）的數量為β，β是一個介于0和1之間的隨機數字。一般而言為了保證算法的收斂速度，β是要小于0.5的。由此成年獅子數量（nLeader）可以表示為：Nβ（1）母獅移動范圍擾動因子af幼獅移動范圍擾動因子ac算法開始，獅王將占有最優秀的位置，此后獅王在最優位置附近小范圍移動，獅王的位置更新公式為：（2）其中，用Xi來代表是獅群中的第i個獅子。gk母獅在捕獵過程中和其他母獅相互協作，位置更新公式為：（3）其中，pc幼獅有三種行為模式，向獅王移動，在獅王附近進食；在母獅附近移動跟母獅學習捕獵；被驅趕到遠離獅王的位置，更新公式如下：（4）其中，pmk表示幼獅跟隨母獅個體的第k代歷史最優位置。算法步驟：step1：初始化獅群，確定各種參數。step2：計算獅王和母獅的數量。確定個體最優位置，將群體最有位置給獅王step3：更新獅王，母獅，幼獅位置。step4：計算獅群的適應度，更新每個獅子的個體歷史最有位置，判斷是否滿足結束條件（一般為迭代次數），滿足轉step6，否則轉step5。step5：過大約10次迭代后，根據位置的優劣重新進行分配，對獅王，母獅，幼獅的位置進行更新，轉step3．。step6：獅王占據著群體最優秀的位置，其所代表的便是最優的解法。算法結束。3.3對獅群算法的改進3.3.1基站分散法根據實驗發現，獅群算法雖然能夠結合歷史最優解進行探索，但是探索仍然還是具有一定的盲目性的。而且獅群算法最后是對所有基站的布局，進行的總體評價，卻不能保證每一個基站的位置都一定能是最佳。其結果就是，基站的信號具有一定的重復率，無法取得最優的解法。本文對獅群算法的探索部分進行了改進，基站的位置將不僅僅由獅王（歷史最優解）和母獅來決定，每一次迭代之后，本文會隨機抽取一個基站，如果發現和它重復率比較高的基站的話，就將這幾個基站分開。然后好比小球之間的不斷撞動一樣，被分開的基站會繼續撞開其他基站，然后依次類推，直到最后所有基站都不會有太大的信號重復。3.3.2具體的算法：文的基站分散法有點類似于廣度優先探索，設置了一個隊列A，和一個數組B。A用來記錄將要被分散的基站，B記錄已經被分散的基站。具體的步驟：步驟1：隨機選取一個基站，放入隊列A中。步驟2：從隊列A中取出一個基站X步驟2：生成一個小于等于兩倍半徑的隨機數字rand，計算其他基站Y和步驟一中基站X的距離，一旦距離小于隨機數字，而且基站Y不屬于數組B（未曾被分散過）且不屬于隊列A（未將被分散），那么將基站Y加入到A中。步驟3：將基站Y進行位置移動，移動公式如下所示。distance=vector=XY這樣的話，堆在一起的基站將會被分散，相互之間的距離是rand（小于等于2倍半徑）。步驟4：將分散結束的基站X放入數組B中，判斷A是否為空，如果為空的話，算法結束。否則轉步驟2.值得一提的是步驟2的隨機生成一個小于等于二倍半徑的隨機數字。實驗中嘗試過將選擇一個固定的數字，比方說2倍半徑，或者1.5倍半徑。但是根據實驗發現，結合獅群算法的情況下，固定的數字缺乏一定的靈活性。有的時候在人口密集的區域，即使犧牲一定的信號覆蓋，也要確保人口的全部覆蓋。相反在人口稀疏的地方，基站則應該盡可能避免信號的重復。本次實驗發現，配合獅群算法，隨機數字的生成可以靈活地探求基站之間的分散距離，提高探索的效率。越界情況的處理：在基站分散的情況下，有的時候會將大量的基站撞到邊界之外去。實驗發現如果將越界的基站隨機放回到界內的話，基站的重復率會比較高。本文的處理方法是，如果有基站越界，那么基站將會從相反的方向重新回到區域內。具體而言的話，是將基站越界時候的點A，關于界的中心進行對稱，得到點B。越界的基站在超過邊界的時候，會保留原有的運動方向，從B開始回到界內。實驗發現，這樣可以避免基站堆在一個角落的情況，可以比較高效地分散基站。關于算法的補充：如同上文所述，本分散算法類似于廣度優先搜索算法，最多的情況下，也不過遍歷所有的基站后便結束。實驗中也嘗試過讓基站不斷地碰撞，以尋求最優的分散結果。但是那樣一則容易進入無限循環，二則的話效果不佳。因而不予采用。第4章基于獅群算法的基站選址4.1關于數據的基本的說明論文設置了一個長44千米，寬44千米的正方形，設置基站可覆蓋地區的半徑為8千米。以下是所采用的參數的列表表4.1參數列表長44km寬44km半徑8km重復次數T2000獅群數量N20維度D（基站數量）10成年時所占比例0.2采樣點數量44*44采樣點距離1km4.2算法的基本流程生成基站初始位置由于維度D（基站數量）為10，所以將一次性生成10個基站，隨機分布在地圖中間。這將作為一種可能的分布。由于獅群數量N為20，所以意味著將會有20種可能的分布被生成。執行“基站分散”。將高度重復的基站分開。對獅群（20種可能的分布）進行適應值的分析本文根據人口的覆蓋率來對獅子（解）來進行評價。在區域內，每隔1km就設一個取樣點。根據勾股定理，計算基站和取樣的距離，如果小于半徑，則視該取樣點已經被覆蓋。記錄下最優解。執行獅群算法根據獅群算法，不斷迭代獅子的位置。同時每次對獅子的位置進行更新后，都進行基站分散，消除對于重復的基站這一情況的探索。基站分散后，對獅群進行適應值的分析，記錄下最優解。判斷是否結束本文設定設定執行重復次數T為2000，執行步驟（3）2000遍后，結束探索。4.3運算的結果與分析：本文采取運行十次后，計算所得人口覆蓋率的平均值。所采用的地圖如下所示，顏色深處代表人口密度高，顏色淺的地方，則代表人口密度低。論文以上下兩個藍色區域代表繁華區，中間的藍色區域代表城市中的相對繁華地帶，四邊代表人口稀疏地帶。運算后的結果如下圖所示：圖4.1信號覆蓋的結果可以看得出來，獅群算法+基站分散法可以覆蓋住人口密度大的區域，同時將基站進行比較均勻的分布。基站分散法在避免基站的高度重疊的基礎上，也允許基站有小規模的重疊，以保證對于關鍵區域的信號覆蓋。為了進一步探究本算法的性質，下表是對算法中的參數進行改變的結果。本文將進行基站分散的獅群算法和未進行基站分散的獅群算法進行了對比。表4.2算法對比算法迭代次數T獅群數量人口覆蓋率獅群算法+基站分散1002091.5%50093.8%100094.3%200094.9%500095.2%1000095.1%1200095.2%10003094.1%6094.7%10094.2%20094.4%1000020095.6%獅群算法1002086.8%50088.6%100088.9%200089.4%500090.6%1000090.8%1200091.4%10003089.7%6090.4%10091.6%20091.7%1000020092.2%可以看得出來隨著迭代次數的增加，覆蓋率有了不小的提高。這不難理解，畢竟迭代次數代表著基站分布的不斷嘗試。隨著嘗試次數的增加，得到好結果的可能性也就越大。隨著獅群數量的增加，獅群算法的結果得到了提升。獅群數量意味著平行進行的探索嘗試的數量，獅群數量的增加帶來覆蓋率的提高也不難理解。綜合結果來看，對于獅群算法+基站分散而言，重復次數為2000，獅群數量是20的話，可以取得比較優秀的結果。論文分析是基站分散將重復的基站直接分開，取得了局部的最優解。但是單純分散基站并不意味著全局的最優，而通過獅群算法對于全局最優解的不斷探索，獅群算法+基站分散能取得一個比較好的結果。不過值得一提的是，獅群算法+基站分散并沒有得到獅群數量增加帶來的恩惠。論文認為這是因為基站分散法已經大大降低了需要探索的位置（不需要探索基站高度重疊的狀態），同時進行的平行探索效果不是很大。對于獅群算法+基站分散而言，重要的是在原先探索基礎所進行的的迭代。同時在比較雙方的極限狀態（重復次數10000次+獅群數量200），基站分散+獅群算法的效果仍然比單純的獅群算法要有提高。可以看見，基站分散這一方法不僅加快了基站選址的過程，對最終的結果也有所提高。圖4.2獅群算法有無“基站分散”的結果對比由上圖表可以看到，獅群算法+基站選址可以縮小需要探索的空間，加快探索的速度，在更短的迭代次數中得到更好的結果。進行了2000次迭代之后獅群算法+基站分散已經接近收斂，可以得到比較優秀的解。相反獅群算法在5000次之后結構仍然沒有收斂，還有待提高。4.4針對其他人口分布的測試：考慮到現實生活中，人口分布情況復雜，本文設計了其他可能的人口分布，并對其進行了測試。由于獅群算法+基站分散在重復次數2000，獅群數量20的時候，已經比較接近收斂的取值。綜合考慮運行時間和結果的情況下，重復次數2000，和獅群數量20的基礎上，進行以下的測試。(a)(b)(c)(d)(e)(f)使用獅群算法+基站分散進行測試。測試之后的結果如下所示。(a)(b)(c)(d)(e)(f)人口分布abcdef人口覆蓋率90.1%94.1%92.2%94.1%93.8%93.5%可以看見，隨著人口分布的不同，基站的分布也隨之發生變化，但是無論哪種人口分布，基站都重點覆蓋住人口密集的區域。而在人口稀疏的區域則相對均勻的分布，以達到盡可能大的覆蓋面積。從最終的結果來看，雖然覆蓋率有高有低，但是整體的分布比較均勻，對人口都實現了一個可以滿足的分布。獅群算法+基站分散的效果還是可以肯定的。4.5單純的基站分散本文還對沒有獅群算法的基站分散法進行了測試，以進一步探究獅群算法的效能。單純的基站分散的想法比較簡單。將基站隨機分布在地圖上，然后進行“基站分散”分散開高度重疊的基站。將這一步驟重復執行，從中選取最優秀的結果。本次實驗“基站分散”會將重疊的基站分散至2個半徑（沒有重疊）。圖4.3單純的基站分散的結果圖4.3是只用基站分散的結果圖。可以看得出來，和設定相符，重復的基站被分散至了2個半徑。基站整體分布雖然比較均勻，人口密集的地方也進行了重點的覆蓋，但是基站和基站的夾角之間的覆蓋效果，不是非常理想。圖4.4獅群算法+基站分散和基站分散的結果對比圖4.4是有無獅群算法對于基站分散的影響。可以看得出來基站分散可以取得一定的效果。雖然每次迭代只是隨機生成初始位置，然后分散基站，但是隨著隨機嘗試的增加，效果還是得到提升。不過由于缺乏記憶進化功能，在得到一個優秀結果后，無法在其基礎上進一步發展。而且由于采取了分散固定長度的做法，無法靈活地覆蓋住基站與基站地邊角位置。最佳效果上是比不過獅群算法+基站分散的聯合算法。4.6PSO+基站分散：為了進一步驗證本文所提出的“基站分散”的適用性，本文選取了與獅群算法同為智能算法的粒子群算法（PSO），在其基礎上增加了“基站分散”，并將其與單純的PSO進行對比。本文的PSO的粒子群數量為60，兩個學習因子均為2，慣性為0.8和0.4。如果發現重疊的基站，基站分散將重疊的基站分散1.8半徑。經過發現，與獅群算法中采用的隨機數字不同，PSO采用分散固定長度的結果比較好圖4.5為PSO+基站分散的結果圖。圖4.5PSO+基站分散的結果圖4.6PSO+基站分散和PSO的對比圖圖4.6是基站分散對于PSO的結果改善的圖。可以看得出來對于PSO，“基站分散”也同樣可以加快探索的速度，縮短收束的時間，取得更加優秀的效果。第5章結論在通信技術飛速發展，5G改變人們生活的時代，基站的建設要求也越來越大。對于網絡與運營商而言，通信基站的建設將會涉及大量的金錢投入，如果能夠更為高效地建設基站，無疑將會對網絡的建設效果起到巨大的貢獻。在使用獅群算法的時候，發現獅群算法在未經充分迭代的情況下，非常容易出現基站重疊的問題。為了取得對人口的充分覆蓋，本文采取了“基站分散法”，改善了獅群算法在探索時候的盲目探索，顯著縮短了迭代次數，并且提升了最后的效果。在參考其他文獻的時候，雖然眾多文獻都對算法提出了不少優秀的改進方法，但是這些改進大都是從算法的角度上進行改善，很少有文獻從實際問題的性質上著手，思考改善方案。本文通過“基站分散法”，從一開始就排除了對于基站信號重復這一可能性的探索，大大提高了探索的效率。之后，本文還可以從以下方面進行改進：（1）本文并未對于地形進行過多的考慮。未來可以考慮障礙物，或者說基站布置的高度對基站覆蓋范圍的影響。通識本文主要考慮的是人口密度的覆蓋，并沒有重視地區的信號覆蓋率。未來