最優(yōu)DT路線規(guī)劃
作者：大木叉叉
郵箱：destild@sina.com
摘要：無線網(wǎng)絡(luò)的RF(Radio Frequency)優(yōu)化是檢測網(wǎng)絡(luò)覆蓋的重要手段，尤其是在LTE網(wǎng)絡(luò)的單站驗(yàn)證、簇優(yōu)化中。DT(Drive Test)路線規(guī)劃是RF優(yōu)化的第一步，最優(yōu)DT路線可以理解為在最短測試?yán)锍痰臈l件下遍歷所有的待測道路。在大范圍(市、區(qū)級(jí)別)的DT測試中，即拉網(wǎng)測試，路線規(guī)劃是必不可少的。該類測試具有時(shí)間長、范圍廣、路線復(fù)雜、重復(fù)道路多等特點(diǎn)�；谠擃悊栴}進(jìn)行研究，本文給出了最短測試路徑規(guī)劃的參考方案，并通過計(jì)算機(jī)算法實(shí)現(xiàn)路線的自動(dòng)規(guī)劃。
關(guān)鍵詞：RF優(yōu)化；DT測試；最優(yōu)路線規(guī)劃；中國郵路問題
1. RF優(yōu)化與路線規(guī)劃
1.1 RF優(yōu)化概要
RF(Radio Frequency)優(yōu)化是指對(duì)無線射頻信號(hào)的優(yōu)化，其目的是根據(jù)系統(tǒng)的實(shí)際表現(xiàn)對(duì)系統(tǒng)進(jìn)行分析，并通過對(duì)網(wǎng)絡(luò)資源和系統(tǒng)參數(shù)的調(diào)整，使系統(tǒng)性能逐步得到改善，達(dá)到系統(tǒng)現(xiàn)有配置條件下的最優(yōu)服務(wù)質(zhì)量。RF優(yōu)化的主要目標(biāo)包括：覆蓋優(yōu)化、容量優(yōu)化以及質(zhì)量優(yōu)化。RF優(yōu)化的基本思想：關(guān)注網(wǎng)絡(luò)的覆蓋、容量、質(zhì)量等，通過覆蓋調(diào)整，干擾調(diào)整，參數(shù)調(diào)整，故障處理等等各種網(wǎng)絡(luò)優(yōu)化手段達(dá)到網(wǎng)絡(luò)動(dòng)態(tài)平衡，提高網(wǎng)絡(luò)質(zhì)量，保障用戶感知[1]。
RF優(yōu)化的基本流程可以用如下的流程圖表示：
路測可以分為DT(Drive Test)和CQT(Call Quality Test)，DT測試主要包括：覆蓋是否正常、扇區(qū)有無接反、扇區(qū)方位角是否和規(guī)劃一致、切換是否正常、業(yè)務(wù)是否正常等等。DT路測路線選取應(yīng)該遵循如下的原則：
1) 測試路線應(yīng)包含主要街道、重要地點(diǎn)和VIP區(qū)域；
2) 為了保證基本的優(yōu)化效果，測試路線應(yīng)盡量包括所有小區(qū)，并且測試路線應(yīng)遍歷所有小區(qū)；
3) 為了準(zhǔn)確地比較性能變化，每次路測是最好固定相同的路測線路；
4) 重復(fù)測試路線要區(qū)分表示，在規(guī)劃線路中，會(huì)不可避免的出現(xiàn)交叉和重復(fù)的情況，盡量減少重復(fù)測試的路線。
路測是RF優(yōu)化的一個(gè)重要的組成部分，路測的第一步就是路測道路規(guī)劃。
1.2路線規(guī)劃
為了便于闡述，假設(shè)測試道路如圖1.所示，其中所有的道路都是雙向可達(dá)的，道路交叉節(jié)點(diǎn)用字母{A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P}表示，各相鄰節(jié)點(diǎn)之間的距離為1個(gè)單位。對(duì)于圖1.所示的交通道路，根據(jù)不同的測試需求，可以規(guī)劃出不同的測試方案，如圖2.所示。
圖1.理想測試道路圖
圖2.不同測試方案的對(duì)比圖
方案1依次通過的節(jié)點(diǎn)為： A B C D H L P O N M I E A B F J N O K G C D H G F E I J K L；方案2依次通過的節(jié)點(diǎn)為： A B C D H G F E I J K L P O N M I E A B F J N O K G C D H L P；方案3依次通過的節(jié)點(diǎn)為： A B F E A B C G F B C D H G C D H L K G H L P O K L P O N J K O N M I J N M I E F J；
在不考慮測試需求的情況下，圖.2中三種不同的測試方案所花費(fèi)的里程比為29：30：42，顯然方案3走的重復(fù)道路是最多的，所以方案3的“代價(jià)”也是最大的。現(xiàn)在我們期望以最小的里程走完所有的路，即不走或者盡量少走重復(fù)路，這就是本文所研究的最小代價(jià)的路線規(guī)劃問題。
2. 路線規(guī)劃的數(shù)學(xué)模型
2.1 Konigsberg七橋問題
最短路線規(guī)劃問題，也就是一筆畫問題起源于瑞士數(shù)學(xué)家萊昂哈德·歐拉(Leonhard Euler)的Konigsberg七橋問題[2]。在所有橋只走一遍的前提下，如何才能把所有的橋走遍。七橋問題可以簡化成點(diǎn)線模型，其中陸地用{A,B,C,D}四個(gè)點(diǎn)來表示，七座橋用相應(yīng)的點(diǎn)之間的連線表示。如圖3.所示：
圖3.七橋問題模型
為了便于問題的闡述，首先給出圖論里面的一些概念的定義。一個(gè)圖(Graph) G=(V,E)由定點(diǎn)(vertex)的集合V和邊(edge)的集合E組成。每一條邊都是一副點(diǎn)對(duì)(v,w)，如果點(diǎn)對(duì)是有序的，那么圖就稱之為有向圖。如果在一個(gè)無向圖中每一個(gè)頂點(diǎn)到每個(gè)其他的點(diǎn)都存在一條路徑，則稱該無向圖是連通的。交通圖可以用一個(gè)圖來模型化，每一條街道交叉口表示一個(gè)頂點(diǎn)，而每一條街道就表示一條邊。圖中的一條路徑(path)是一個(gè)頂點(diǎn)序列w1,w2,w3,...,wn使得(wi,wi+1)∈E,1<i≤N，這樣一條路徑的長(length)是為該路徑上的邊數(shù)，它等于N-1。歐拉環(huán)游(Euler circuit)問題即尋找圖中的一條路徑，使得該路徑訪問圖的每條邊恰好一次。設(shè)無向圖G(V,E)為連通圖，若邊E1∈E，在圖G中刪除E1得到的子圖示不連通的，則稱E1是圖G橋。給出了歐拉環(huán)游存在的條件。歐拉定理
1. 當(dāng)圖是連通的并且每個(gè)頂點(diǎn)的度(邊的條數(shù))是偶數(shù)。
2. 如果恰有兩個(gè)頂點(diǎn)的度是奇數(shù)，歐拉環(huán)游從一個(gè)奇數(shù)度的頂點(diǎn)出發(fā)終止在另一個(gè)奇數(shù)度的頂點(diǎn)。
2.2 中國郵路問題
歷史總是驚人的相似，早在60年代我國學(xué)者管梅谷根據(jù)實(shí)際問題的需要對(duì)于該類路線規(guī)劃問題進(jìn)行了研究，即著名的中國投遞員問題[3]，就是：“一個(gè)投遞員應(yīng)該怎樣選擇一條路線，才能既走遍由他負(fù)責(zé)送信的所有街道，而所走的路程又最短�！痹擃悊栴}的解決方案用圖論的術(shù)語可以敘述為：
“設(shè)E1是圖G=(V,E)的一個(gè)邊集，若把E1中的邊加入G中（作為重復(fù)邊），得到的圖G’所有的頂點(diǎn)的度均為偶次，就稱E1為一組可行解，總長度最短的可行解叫做最優(yōu)解。不難看出，可行解一般可以看成是一些吧G的奇次頂點(diǎn)一對(duì)一對(duì)地連接起來的鏈。由于G’沒有奇次度的頂點(diǎn)，即圖G’存在歐拉環(huán)游�！�
3. 路線規(guī)劃與算法設(shè)計(jì)
根據(jù)歐拉總結(jié)的規(guī)律，對(duì)于七橋問題顯然是不存在答案的。那么如何去實(shí)現(xiàn)最短路線走完七橋呢？聯(lián)系到實(shí)際中，如果我們?cè)诼窚y這樣的七條道路，我們?nèi)绾文軌虮M快的走完這里的七條路，這對(duì)于現(xiàn)實(shí)有著很重要的指導(dǎo)意義。
3.1 路線規(guī)劃
根據(jù)歐拉定理，規(guī)劃圖.1的測試路線。
第一步：構(gòu)造偶數(shù)點(diǎn)連線
圖.1中，從節(jié)點(diǎn)B,C,E,H,I,L,N,O出發(fā)的路線都是奇數(shù)條，把這些基數(shù)點(diǎn)用一條輔助道路兩兩連接，使圖滿足歐拉回路的條件。而這條虛擬的輔助道路的實(shí)際意義就是在實(shí)際行走的過程中需要重復(fù)走過的道路。這樣我們就可以清晰的設(shè)計(jì)出要重復(fù)走的路，而且把重復(fù)走的路縮減到最少。根據(jù)這個(gè)基本的思路，構(gòu)造如圖.4的歐拉圖：
圖4.添加輔助道路的歐拉回路圖
如圖4.所示，道路Q、R、S、T是添加的輔助點(diǎn)及輔助道路，添加完輔助道路后的圖所有的節(jié)點(diǎn)都是偶數(shù)節(jié)點(diǎn)。所以圖4為Euler圖且必存在Euler環(huán)游。
第二步：設(shè)計(jì)歐陸路徑
添加了輔助道路的測試路徑滿足歐拉回路的條件，所以必定是能夠構(gòu)造出若干條歐拉路徑的。如圖5.所示。
通過圖5.所給出的歐拉路徑可以看出，重復(fù)走過的路線包括BC，HL，ON，IE，更為重要的是這些重復(fù)的路徑是可以人為選定設(shè)計(jì)的。與圖2所給出的方案相比，圖4的方案重復(fù)路線是最少的，他們所花費(fèi)的里程之比是28：29：30：42。
圖.5 帶有輔助道路的歐拉路徑
3.2 算法設(shè)計(jì)
在實(shí)際的DT過程中，常常會(huì)出現(xiàn)道路多，路況復(fù)雜的情況。為此我們借用計(jì)算機(jī)編程輔助我們來設(shè)計(jì)Euler環(huán)游。首先建立測試道路的數(shù)學(xué)模型。以圖1.的測試道路為例，該圖主要由16個(gè)節(jié)點(diǎn)（A~P）及其之間的連線組成，構(gòu)造圖4的16×16的矩陣模型。其中每一行（列）分別表示某一個(gè)節(jié)點(diǎn)，該行（列）的數(shù)值意義為：1表示兩點(diǎn)之間存在道路，0表示兩點(diǎn)之間不存在道路，其中節(jié)點(diǎn)自身之間不存在連線。如：(E,G)=0，(K,G)=1表示節(jié)點(diǎn)E和G之間沒有連線而節(jié)點(diǎn)K和G之間存在連線。
圖6.測試道路的矩陣模型
參考Fleury算法[4]，編寫程序來搜索Euler環(huán)游，
結(jié)果輸出為：
表1.策略表
3.3 實(shí)際應(yīng)用
基站發(fā)出的載波信號(hào)在空中傳播過程中，由于地形、建筑物及其他一些環(huán)境因素的影響，或者受到實(shí)際建設(shè)時(shí)基站選址上的不確切性及網(wǎng)絡(luò)運(yùn)行中基站周圍環(huán)境發(fā)生較大的變化的因素的影響，使得系統(tǒng)實(shí)際建成以后的覆蓋情況發(fā)生了較大的變化。因此只有通過實(shí)地的測量才能真正了解系統(tǒng)的實(shí)際覆蓋情況。
通過路測可以準(zhǔn)確記錄測試過程中的位置信息、事件信息、地貌信息和覆蓋情況，對(duì)于基站覆蓋區(qū)域有一個(gè)全面的了解。
如圖7.北京市二環(huán)內(nèi)主要道路分布圖(二環(huán)道路圖)所示，對(duì)于北京市二環(huán)內(nèi)(含二環(huán))的主干道路進(jìn)行DT測試。測試要求1.走完所有的道路；2.重復(fù)測試路線盡量減少。
圖7.北京市二環(huán)內(nèi)主要道路分布圖
對(duì)于北京市二環(huán)道路測試，為了簡化模型，首先我們進(jìn)行如下假設(shè)：任意存在連接的兩個(gè)節(jié)點(diǎn)之間都是連通，且雙向可達(dá)。通過程序可以得出如下策略：
通過表1.可以看出，在405步之后，可以遍歷完圖7.中所有的道路，重復(fù)測試的道路用紅色在圖7.中標(biāo)出。
表2. 策略表
4.總結(jié)
在進(jìn)行RF優(yōu)化的過程中，遇到了最短DT測試路線規(guī)劃問題。為了更加解決該類問題，同時(shí)節(jié)約測試成本提高測試效率，對(duì)于該類問題進(jìn)行了深入的研究。在建立實(shí)際問題的數(shù)學(xué)模型時(shí)，才恍然發(fā)現(xiàn)對(duì)于該類問題前輩學(xué)者已經(jīng)有了深入的研究并給出最優(yōu)路線規(guī)劃方案。借鑒前人的研究成果，利用現(xiàn)代的計(jì)算機(jī)算法，根據(jù)DT測試問題的特性，最終給出合理的解決方案。
參考文獻(xiàn)
[1] 林世明,高志斌,高鳳連,黃聯(lián)芬.基于路測的TD-LTE網(wǎng)絡(luò)優(yōu)化分析[A],現(xiàn)代電子技術(shù),2015,(38):12-15
[2] 高中印. 用數(shù)學(xué)建模方法解決哥尼斯堡七橋問題[J]. 河北民族師范學(xué)院學(xué)報(bào), 2010, 30(2):14-15
[3] 管梅谷. 中國投遞員問題綜述[J]. Journal of Mathematical Research with Applications(數(shù)學(xué)研究與應(yīng)用(英文)), 1984, 4(1):113-119.
[4] 呂義忠. 關(guān)于Fleury算法的一點(diǎn)注記[J]. 南京航空航天大學(xué)學(xué)報(bào), 1998(4):470-472
關(guān)注樓主