最優(yōu)DT路線規(guī)劃

作者：大木叉叉

郵箱：destild@sina.com

摘要：無線網(wǎng)絡的RF(Radio Frequency)優(yōu)化是檢測網(wǎng)絡覆蓋的重要手段，尤其是在LTE網(wǎng)絡的單站驗證、簇優(yōu)化中。DT(Drive Test)路線規(guī)劃是RF優(yōu)化的第一步，最優(yōu)DT路線可以理解為在最短測試里程的條件下遍歷所有的待測道路。在大范圍(市、區(qū)級別)的DT測試中，即拉網(wǎng)測試，路線規(guī)劃是必不可少的。該類測試具有時間長、范圍廣、路線復雜、重復道路多等特點。基于該類問題進行研究，本文給出了最短測試路徑規(guī)劃的參考方案，并通過計算機算法實現(xiàn)路線的自動規(guī)劃。

關鍵詞：RF優(yōu)化；DT測試；最優(yōu)路線規(guī)劃；中國郵路問題

1. RF優(yōu)化與路線規(guī)劃

1.1 RF優(yōu)化概要

RF(Radio Frequency)優(yōu)化是指對無線射頻信號的優(yōu)化，其目的是根據(jù)系統(tǒng)的實際表現(xiàn)對系統(tǒng)進行分析，并通過對網(wǎng)絡資源和系統(tǒng)參數(shù)的調(diào)整，使系統(tǒng)性能逐步得到改善，達到系統(tǒng)現(xiàn)有配置條件下的最優(yōu)服務質(zhì)量。RF優(yōu)化的主要目標包括：覆蓋優(yōu)化、容量優(yōu)化以及質(zhì)量優(yōu)化。RF優(yōu)化的基本思想：關注網(wǎng)絡的覆蓋、容量、質(zhì)量等，通過覆蓋調(diào)整，干擾調(diào)整，參數(shù)調(diào)整，故障處理等等各種網(wǎng)絡優(yōu)化手段達到網(wǎng)絡動態(tài)平衡，提高網(wǎng)絡質(zhì)量，保障用戶感知[1]。

RF優(yōu)化的基本流程可以用如下的流程圖表示：

路測可以分為DT(Drive Test)和CQT(Call Quality Test)，DT測試主要包括：覆蓋是否正常、扇區(qū)有無接反、扇區(qū)方位角是否和規(guī)劃一致、切換是否正常、業(yè)務是否正常等等。DT路測路線選取應該遵循如下的原則：

1)      測試路線應包含主要街道、重要地點和VIP區(qū)域；

2)      為了保證基本的優(yōu)化效果，測試路線應盡量包括所有小區(qū)，并且測試路線應遍歷所有小區(qū)；

3)      為了準確地比較性能變化，每次路測是最好固定相同的路測線路；

4)      重復測試路線要區(qū)分表示，在規(guī)劃線路中，會不可避免的出現(xiàn)交叉和重復的情況，盡量減少重復測試的路線。

路測是RF優(yōu)化的一個重要的組成部分，路測的第一步就是路測道路規(guī)劃。

1.2路線規(guī)劃

為了便于闡述，假設測試道路如圖1.所示，其中所有的道路都是雙向可達的，道路交叉節(jié)點用字母{A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P}表示，各相鄰節(jié)點之間的距離為1個單位。對于圖1.所示的交通道路，根據(jù)不同的測試需求，可以規(guī)劃出不同的測試方案，如圖2.所示。

圖1.理想測試道路圖

圖2.不同測試方案的對比圖

方案1依次通過的節(jié)點為： 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é)點為： 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é)點為： 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中三種不同的測試方案所花費的里程比為29：30：42，顯然方案3走的重復道路是最多的，所以方案3的“代價”也是最大的�，F(xiàn)在我們期望以最小的里程走完所有的路，即不走或者盡量少走重復路，這就是本文所研究的最小代價的路線規(guī)劃問題。

2. 路線規(guī)劃的數(shù)學模型

2.1 Konigsberg七橋問題

最短路線規(guī)劃問題，也就是一筆畫問題起源于瑞士數(shù)學家萊昂哈德·歐拉(Leonhard Euler)的Konigsberg七橋問題[2]。在所有橋只走一遍的前提下，如何才能把所有的橋走遍。七橋問題可以簡化成點線模型，其中陸地用{A,B,C,D}四個點來表示，七座橋用相應的點之間的連線表示。如圖3.所示：

圖3.七橋問題模型

為了便于問題的闡述，首先給出圖論里面的一些概念的定義。一個圖(Graph) G=(V,E)由定點(vertex)的集合V和邊(edge)的集合E組成。每一條邊都是一副點對(v,w)，如果點對是有序的，那么圖就稱之為有向圖。如果在一個無向圖中每一個頂點到每個其他的點都存在一條路徑，則稱該無向圖是連通的。交通圖可以用一個圖來模型化，每一條街道交叉口表示一個頂點，而每一條街道就表示一條邊。圖中的一條路徑(path)是一個頂點序列w₁,w₂,w₃,...,w_n使得(w_i,w_i+1)∈E,1<i≤N，這樣一條路徑的長(length)是為該路徑上的邊數(shù)，它等于N-1。歐拉環(huán)游(Euler circuit)問題即尋找圖中的一條路徑，使得該路徑訪問圖的每條邊恰好一次。設無向圖G(V,E)為連通圖，若邊E₁∈E，在圖G中刪除E₁得到的子圖示不連通的，則稱E₁是圖G橋。給出了歐拉環(huán)游存在的條件。歐拉定理

1.       當圖是連通的并且每個頂點的度(邊的條數(shù))是偶數(shù)。

2.       如果恰有兩個頂點的度是奇數(shù)，歐拉環(huán)游從一個奇數(shù)度的頂點出發(fā)終止在另一個奇數(shù)度的頂點。

2.2 中國郵路問題

歷史總是驚人的相似，早在60年代我國學者管梅谷根據(jù)實際問題的需要對于該類路線規(guī)劃問題進行了研究，即著名的中國投遞員問題[3]，就是：“一個投遞員應該怎樣選擇一條路線，才能既走遍由他負責送信的所有街道，而所走的路程又最短�！痹擃悊栴}的解決方案用圖論的術語可以敘述為：

“設E₁是圖G=(V,E)的一個邊集，若把E₁中的邊加入G中（作為重復邊），得到的圖G’所有的頂點的度均為偶次，就稱E₁為一組可行解，總長度最短的可行解叫做最優(yōu)解。不難看出，可行解一般可以看成是一些吧G的奇次頂點一對一對地連接起來的鏈。由于G’沒有奇次度的頂點，即圖G’存在歐拉環(huán)游�！�

3. 路線規(guī)劃與算法設計

根據(jù)歐拉總結的規(guī)律，對于七橋問題顯然是不存在答案的。那么如何去實現(xiàn)最短路線走完七橋呢？聯(lián)系到實際中，如果我們在路測這樣的七條道路，我們?nèi)绾文軌虮M快的走完這里的七條路，這對于現(xiàn)實有著很重要的指導意義。

3.1 路線規(guī)劃

根據(jù)歐拉定理，規(guī)劃圖.1的測試路線。

第一步：構造偶數(shù)點連線

圖.1中，從節(jié)點B,C,E,H,I,L,N,O出發(fā)的路線都是奇數(shù)條，把這些基數(shù)點用一條輔助道路兩兩連接，使圖滿足歐拉回路的條件。而這條虛擬的輔助道路的實際意義就是在實際行走的過程中需要重復走過的道路。這樣我們就可以清晰的設計出要重復走的路，而且把重復走的路縮減到最少。根據(jù)這個基本的思路，構造如圖.4的歐拉圖：

圖4.添加輔助道路的歐拉回路圖

如圖4.所示，道路Q、R、S、T是添加的輔助點及輔助道路，添加完輔助道路后的圖所有的節(jié)點都是偶數(shù)節(jié)點。所以圖4為Euler圖且必存在Euler環(huán)游。

第二步：設計歐陸路徑

添加了輔助道路的測試路徑滿足歐拉回路的條件，所以必定是能夠構造出若干條歐拉路徑的。如圖5.所示。

通過圖5.所給出的歐拉路徑可以看出，重復走過的路線包括BC，HL，ON，IE，更為重要的是這些重復的路徑是可以人為選定設計的。與圖2所給出的方案相比，圖4的方案重復路線是最少的，他們所花費的里程之比是28：29：30：42。

圖.5 帶有輔助道路的歐拉路徑

3.2 算法設計

在實際的DT過程中，常常會出現(xiàn)道路多，路況復雜的情況。為此我們借用計算機編程輔助我們來設計Euler環(huán)游。首先建立測試道路的數(shù)學模型。以圖1.的測試道路為例，該圖主要由16個節(jié)點（A~P）及其之間的連線組成，構造圖4的16×16的矩陣模型。其中每一行（列）分別表示某一個節(jié)點，該行（列）的數(shù)值意義為：1表示兩點之間存在道路，0表示兩點之間不存在道路，其中節(jié)點自身之間不存在連線。如：(E,G)=0，(K,G)=1表示節(jié)點E和G之間沒有連線而節(jié)點K和G之間存在連線。

圖6.測試道路的矩陣模型

參考Fleury算法[4]，編寫程序來搜索Euler環(huán)游，

結果輸出為：

表1.策略表

3.3 實際應用

基站發(fā)出的載波信號在空中傳播過程中，由于地形、建筑物及其他一些環(huán)境因素的影響，或者受到實際建設時基站選址上的不確切性及網(wǎng)絡運行中基站周圍環(huán)境發(fā)生較大的變化的因素的影響，使得系統(tǒng)實際建成以后的覆蓋情況發(fā)生了較大的變化。因此只有通過實地的測量才能真正了解系統(tǒng)的實際覆蓋情況。

通過路測可以準確記錄測試過程中的位置信息、事件信息、地貌信息和覆蓋情況，對于基站覆蓋區(qū)域有一個全面的了解。

如圖7.北京市二環(huán)內(nèi)主要道路分布圖(二環(huán)道路圖)所示，對于北京市二環(huán)內(nèi)(含二環(huán))的主干道路進行DT測試。測試要求1.走完所有的道路；2.重復測試路線盡量減少。

圖7.北京市二環(huán)內(nèi)主要道路分布圖

對于北京市二環(huán)道路測試，為了簡化模型，首先我們進行如下假設：任意存在連接的兩個節(jié)點之間都是連通，且雙向可達。通過程序可以得出如下策略：

通過表1.可以看出，在405步之后，可以遍歷完圖7.中所有的道路，重復測試的道路用紅色在圖7.中標出。

表2. 策略表

4.總結

在進行RF優(yōu)化的過程中，遇到了最短DT測試路線規(guī)劃問題。為了更加解決該類問題，同時節(jié)約測試成本提高測試效率，對于該類問題進行了深入的研究。在建立實際問題的數(shù)學模型時，才恍然發(fā)現(xiàn)對于該類問題前輩學者已經(jīng)有了深入的研究并給出最優(yōu)路線規(guī)劃方案。借鑒前人的研究成果，利用現(xiàn)代的計算機算法，根據(jù)DT測試問題的特性，最終給出合理的解決方案。

參考文獻

[1] 林世明,高志斌,高鳳連,黃聯(lián)芬.基于路測的TD-LTE網(wǎng)絡優(yōu)化分析[A],現(xiàn)代電子技術,2015,(38):12-15

[2] 高中印. 用數(shù)學建模方法解決哥尼斯堡七橋問題[J]. 河北民族師范學院學報, 2010, 30(2):14-15

[3] 管梅谷. 中國投遞員問題綜述[J]. Journal of Mathematical Research with Applications(數(shù)學研究與應用(英文)), 1984, 4(1):113-119.

[4] 呂義忠. 關于Fleury算法的一點注記[J]. 南京航空航天大學學報, 1998(4):470-472