一種基于BFS的數(shù)據(jù)鏈站點(diǎn)優(yōu)化選址算法

趙延龍，滑 楠，于振華

（空軍工程大學(xué)信息與導(dǎo)航學(xué)院，西安 710077）

0 引言

目前，針對(duì)數(shù)據(jù)鏈的研究主要集中在數(shù)據(jù)鏈系統(tǒng)建模仿真[1-4]和數(shù)據(jù)鏈網(wǎng)絡(luò)規(guī)劃[5-7]兩方面，然而針對(duì)實(shí)際中數(shù)據(jù)鏈站點(diǎn)優(yōu)化選址的研究相對(duì)較少。文獻(xiàn)[8]中提出了一種引入柵格化方法的數(shù)據(jù)鏈站點(diǎn)選址方法，通過(guò)建立數(shù)學(xué)模型，將站點(diǎn)優(yōu)化問(wèn)題轉(zhuǎn)換為0-1整數(shù)規(guī)劃問(wèn)題，并通過(guò)LINGO軟件對(duì)具體實(shí)例進(jìn)行編程求解，驗(yàn)證了該方法的可行性。數(shù)據(jù)鏈站點(diǎn)選址問(wèn)題與數(shù)據(jù)鏈網(wǎng)絡(luò)規(guī)劃問(wèn)題不同，在文獻(xiàn)[9-10]中已被證明是NP難問(wèn)題，因而當(dāng)問(wèn)題的數(shù)據(jù)規(guī)模很大時(shí)，在現(xiàn)有的計(jì)算條件下很難求得全局最優(yōu)解。

深度優(yōu)先搜索算法（Depth First Search，DFS）[11]與廣度優(yōu)先搜索算法（Breadth First Search，DFS）[12]兩者相同點(diǎn)都是在計(jì)算機(jī)應(yīng)用領(lǐng)域中常用的搜索算法，不同點(diǎn)主要體現(xiàn)在搜索策略方面：DFS算法遵循盡可能深的搜索策略，對(duì)于新發(fā)現(xiàn)的結(jié)點(diǎn)進(jìn)行優(yōu)先擴(kuò)展，一直到某一確定的層為止，如果達(dá)不到目標(biāo)要求則回溯到上一個(gè)結(jié)點(diǎn)繼續(xù)搜索，直到全部遍歷為止；BFS算法遵循在某一層盡可能寬的搜索策略，深度越小的結(jié)點(diǎn)優(yōu)先進(jìn)行搜索，然后逐層擴(kuò)展。

本文采用柵格化思想，綜合考慮地理高程信息對(duì)電磁信號(hào)覆蓋范圍的影響以及特定標(biāo)志點(diǎn)等因素，建立數(shù)據(jù)鏈站點(diǎn)優(yōu)化選址的整數(shù)規(guī)劃模型，并提出一種基于BFS的數(shù)據(jù)鏈站點(diǎn)選址算法（Data-link Site Optimization Location，DSOL），最后通過(guò)具體實(shí)例進(jìn)行驗(yàn)證。

1 數(shù)據(jù)鏈站點(diǎn)優(yōu)化選址模型

傳統(tǒng)的數(shù)據(jù)鏈站點(diǎn)選址作業(yè)往往以人工型、經(jīng)驗(yàn)型為主，科學(xué)性不強(qiáng)，難以充分發(fā)揮數(shù)據(jù)鏈網(wǎng)絡(luò)的通信效能。本文從實(shí)際出發(fā)，采用柵格化的方法對(duì)數(shù)據(jù)鏈站點(diǎn)選址區(qū)域進(jìn)行劃分，綜合考慮電磁信號(hào)覆蓋范圍、特定標(biāo)志點(diǎn)等影響因素建立數(shù)學(xué)模型。

1.1 區(qū)域劃分

本文采用文獻(xiàn)[9]中柵格化的方法對(duì)數(shù)據(jù)鏈站點(diǎn)布設(shè)區(qū)域進(jìn)行區(qū)域劃分，如圖1所示。

圖1 數(shù)據(jù)鏈站點(diǎn)布設(shè)區(qū)域

設(shè)東西南北各相隔T km進(jìn)行采樣取點(diǎn)，地球半徑為R km，將對(duì)應(yīng)的高程數(shù)據(jù)放到矩陣M中，最終獲得高程矩陣的規(guī)模為X×Y，其中：

1.2 電磁信號(hào)覆蓋范圍

數(shù)據(jù)鏈地面站裝備一般為短波和超短波裝備，屬于UHF和VHF波段范圍內(nèi)的無(wú)線通信裝備，主要傳播模式為視距傳播，因此，在某一具體高空處，電磁信號(hào)覆蓋范圍主要受布設(shè)點(diǎn)周圍建筑物或地形的影響，這些影響因素歸結(jié)為受不同地理高程的影響。假設(shè)電磁信號(hào)有效傳播距離為l，信號(hào)源為O，信號(hào)源在某一方向上且在海拔h處的電磁信號(hào)傳播示意圖如圖2所示。

圖2 電磁信號(hào)傳播示意圖

圖2（a）中，在沒(méi)有障礙物阻擋時(shí)，由勾股定理得，電磁信號(hào)在海拔h處的最遠(yuǎn)有效傳播距離為：

圖2（b）中，在有障礙物阻擋時(shí)，電磁信號(hào)在海拔h處的最遠(yuǎn)有效傳播距離取決于不同地理位置處的最高點(diǎn)與信號(hào)源O的最大夾角α和β，即：

將電磁信號(hào)從信號(hào)源O在某一方向上的傳播情況拓展到任意方向上即可得到信號(hào)源O在海拔h處的電磁信號(hào)覆蓋范圍。

1.3 地球曲率對(duì)高程的影響

由于受地球曲率的影響，地球上某一點(diǎn)的實(shí)際高程在視距的影響下會(huì)有一定的偏差，如下頁(yè)圖3所示。

設(shè)B點(diǎn)的實(shí)際高程為h；地球半徑R=6 400 km；OA與OB的夾角為α；A點(diǎn)到B點(diǎn)最高點(diǎn)處的仰角，即；OA垂直于AB；OC垂直于AC；A點(diǎn)到OB的距離為l，即AC=l，由此得出：

圖3 地球曲率對(duì)高程影響示意圖

將式（11）代入式（10）得：

將式（9）、式（12）代入式（8）得：

由式（7）得：

將式（14）代入式（13）得：

從而求得B點(diǎn)在A點(diǎn)處實(shí)際高程為：

1.4 數(shù)學(xué)模型建立

1.4.1 決策變量設(shè)計(jì)

xij：取值0或1。當(dāng)xij=1表示選擇點(diǎn)作為數(shù)據(jù)鏈站點(diǎn)地址；當(dāng)xij=0表示不作為數(shù)據(jù)鏈站點(diǎn)地址；

Sh：表示需滿足在海拔h處的電磁信號(hào)覆蓋范圍。

1.4.2 設(shè)計(jì)優(yōu)化目標(biāo)及約束條件

數(shù)據(jù)鏈站點(diǎn)優(yōu)化選址模型主要從裝備數(shù)量、布設(shè)地點(diǎn)與特定標(biāo)志點(diǎn)的關(guān)系兩方面考慮。

1）裝備數(shù)量盡可能少

其中，X，Y分別表示對(duì)保障區(qū)域采樣后的高程矩陣規(guī)模大小。數(shù)據(jù)鏈要求在給定高度上空處的航路被電磁信號(hào)無(wú)縫覆蓋，即需滿足如下約束條件：

式（18）表示所有布設(shè)點(diǎn)處裝備電磁波信號(hào)覆蓋范圍必須完全包含航路范圍。其中表示即設(shè)數(shù)據(jù)鏈地面站在海拔h處的電磁信號(hào)覆蓋范圍。

2）布設(shè)點(diǎn)盡可能靠近標(biāo)志點(diǎn)

裝備布設(shè)點(diǎn)盡可能靠近標(biāo)志點(diǎn)是指在數(shù)據(jù)鏈實(shí)際組網(wǎng)建鏈過(guò)程中，為了便于實(shí)施保障要求裝備在滿足電磁信號(hào)覆蓋范圍前提下盡可能靠近路口、光纖接入點(diǎn)、水源等正標(biāo)志點(diǎn)，以及為了減少對(duì)居民生活的輻射影響要求盡可能遠(yuǎn)離居民點(diǎn)等負(fù)標(biāo)志點(diǎn)。

式（19）中，R表示道路口的個(gè)數(shù)；rk表示第k個(gè)道路口；表示第k個(gè)道路口在劃分區(qū)域內(nèi)的位置坐標(biāo)；L表示光纖接入點(diǎn)的個(gè)數(shù)；lk表示第k個(gè)光纖接入點(diǎn)；表示第k個(gè)光纖接入點(diǎn)的位置坐標(biāo)；W表示水源的個(gè)數(shù)；wk表示第 k個(gè)水源；表示第k個(gè)水源點(diǎn)的位置坐標(biāo)；Q表示居民點(diǎn)的個(gè)數(shù)；qk表示第k個(gè)居民點(diǎn)；表示第k個(gè)居民點(diǎn)的位置坐標(biāo)；表示裝備布設(shè)地點(diǎn)與相應(yīng)標(biāo)志點(diǎn)rk之間的距離。分別表示裝備布設(shè)地點(diǎn)與4種不同標(biāo)志點(diǎn)之間距離的權(quán)值。權(quán)值為正表示正標(biāo)志點(diǎn)，為負(fù)則表示負(fù)標(biāo)志點(diǎn)，并且絕對(duì)值越大，表示該類標(biāo)志點(diǎn)對(duì)裝備布設(shè)地點(diǎn)的重要程度就越高。

2 數(shù)據(jù)鏈站點(diǎn)選址算法DSOL

在整數(shù)規(guī)劃問(wèn)題中，最可靠的求解方法為枚舉法，這種方法枚舉出每一種可行解，最終求出全局最優(yōu)解，然而枚舉法最大的缺陷是當(dāng)問(wèn)題的規(guī)模較大時(shí)，時(shí)間復(fù)雜度O（2n）將會(huì)急劇增大。因此，有學(xué)者提出隱枚舉法[13]來(lái)解決整數(shù)規(guī)劃問(wèn)題，它的基本思想是忽略不可行組合方案，只檢查部分可行組合方案，雖然在一定程度上減少花費(fèi)時(shí)長(zhǎng)，但算法時(shí)間復(fù)雜度仍然為 O（2n）。

數(shù)據(jù)鏈站點(diǎn)選址模型中，由于第一個(gè)子目標(biāo)函數(shù)為裝備盡可能少，即組合方案中“1”的個(gè)數(shù)盡可能少，因此，模型的規(guī)模是動(dòng)態(tài)變化的。DFS算法中，首先需要確定搜索的層數(shù)，模型的規(guī)模為固定的；而BFS算法是按照層次不斷向外擴(kuò)展，模型的規(guī)模是動(dòng)態(tài)變化的，因此，BFS算法更適合數(shù)據(jù)鏈站點(diǎn)優(yōu)化選址模型的求解。

2.1 DSOL算法基本思想

為便于利用BFS算法對(duì)優(yōu)化選址模型進(jìn)行求解，需要引入覆蓋矩陣Pij、判別矩陣Q、距離矩陣Dij以及目標(biāo)矩陣S。

2.1.1 覆蓋矩陣Pij

2.1.2 判別矩陣Q

其中，qij取值0或1。1表示覆蓋，0表示未覆蓋。

2.1.3 距離矩陣Dij

2.1.4 目標(biāo)矩陣S

其中，sij取值0或1。1表示覆蓋，0表示不覆蓋。

DSOL算法的基本思想是從判別矩陣中選擇一個(gè)非零點(diǎn)o作為初始點(diǎn)；從o點(diǎn)開(kāi)始按照廣度優(yōu)先依次向外層進(jìn)行搜索，即在覆蓋矩陣中查找與o點(diǎn)相關(guān)聯(lián)且能覆蓋目標(biāo)區(qū)域S的其他點(diǎn)；判斷在所有已選擇點(diǎn)處布設(shè)數(shù)據(jù)鏈地面站的電磁信號(hào)是否滿足完全覆蓋目標(biāo)區(qū)域S，如果滿足，則選擇距離特定標(biāo)志點(diǎn)較近的方案，否則繼續(xù)搜索。

2.2 DSOL算法實(shí)現(xiàn)

依據(jù)DSOL算法的基本思想，得到的算法流程圖如圖4所示。

圖4 DSOL算法流程圖

3 仿真分析

為驗(yàn)證基于BFS算法的數(shù)據(jù)鏈站點(diǎn)優(yōu)化選址算法DSOL的有效性，本文利用Matlab2016a軟件，在硬件環(huán)境Intel 3.2 GHz，內(nèi)存4 GB和軟件環(huán)境Microsoft Windows 7仿真實(shí)驗(yàn)環(huán)境條件下對(duì)數(shù)據(jù)鏈補(bǔ)盲典型案例進(jìn)行仿真驗(yàn)證。

3.1 數(shù)據(jù)鏈補(bǔ)盲典型案例

如圖1所示的數(shù)據(jù)鏈站點(diǎn)布設(shè)區(qū)域，假設(shè)經(jīng)過(guò)1.1區(qū)域劃分處理后的區(qū)域如下頁(yè)圖5所示。

圖5 柵格化后的布設(shè)區(qū)域

現(xiàn)有XXX型殲擊機(jī)需在3 km高空處從A（2，7）地經(jīng) B（4，2）地飛往 C（8，4）地執(zhí)行巡邏任務(wù)。已知既設(shè)數(shù)據(jù)鏈地面站布設(shè)位置為A、B、C 3點(diǎn)，并且在3 km高空處未能完全覆蓋；道路口R1（2，3）、R2（8，2），光纖接入點(diǎn)L（4，5），水源W（5，4），居民點(diǎn)Q（5，1）；，。求需補(bǔ)盲的最少的數(shù)據(jù)鏈站點(diǎn)以及在布設(shè)區(qū)域中相對(duì)應(yīng)的位置。

3.2 計(jì)算覆蓋矩陣Pij

假設(shè)在圖5布設(shè)區(qū)域中的一點(diǎn)X（i，j）處布設(shè)數(shù)據(jù)鏈地面站后，電磁信號(hào)覆蓋范圍為包含點(diǎn)X在內(nèi)的周圍共9個(gè)布設(shè)點(diǎn)所在的區(qū)域，分為3種情形，分別如式（24）～式（26）所示。

式（24）中，P11表示在布設(shè)區(qū)域4個(gè)角處的電磁信號(hào)覆蓋情況；式（25）中，P14表示在布設(shè)區(qū)域4條邊上的電磁信號(hào)覆蓋情況；式（26）中，P45表示在布設(shè)區(qū)域內(nèi)部的電磁信號(hào)覆蓋情況。

3.3 計(jì)算判別矩陣Q及目標(biāo)矩陣S

判別矩陣中的元素qij表示在位置（i，j）處布設(shè)數(shù)據(jù)鏈地面站時(shí)對(duì)目標(biāo)區(qū)域的覆蓋情況，從圖5中分析得出，判別矩陣Q和目標(biāo)矩陣S分別如式（27）、式（28）所示。

最終通過(guò)Matlab2016a仿真平臺(tái)，采用DSOL算法計(jì)算出的布設(shè)矩陣：

即所需布設(shè)的最少數(shù)數(shù)據(jù)鏈地面站為3；最優(yōu)布設(shè)方案為（3，4）、（3，7）、（6，3）。算法花費(fèi)時(shí)間為0.012 435 s。

為驗(yàn)證DSOL算法的正確性和有效性，將文獻(xiàn)[9]中利用Lingo軟件優(yōu)化數(shù)據(jù)鏈站點(diǎn)選址的方法與本文所提的DSOL算法進(jìn)行對(duì)比仿真實(shí)驗(yàn)。優(yōu)化目標(biāo)為使得f1+f2值最小。程序代碼設(shè)計(jì)為：

仿真結(jié)果如圖6所示。

圖6 Lingo仿真實(shí)驗(yàn)結(jié)果

通過(guò)Lingo軟件對(duì)數(shù)據(jù)鏈補(bǔ)盲案例進(jìn)行優(yōu)化，所求得全局最優(yōu)布設(shè)方案為（3，4）、（3，7）、（6，3），最少布設(shè)數(shù)量為3，與本文所提算法DSOL求解結(jié)果一致，從而驗(yàn)證了DSOL求解結(jié)果的正確性；DSOL算法求解花費(fèi)時(shí)長(zhǎng)為0.012 435 s，而通過(guò)Lingo進(jìn)行求解所需花費(fèi)時(shí)長(zhǎng)為1 s，遠(yuǎn)大于利用DSOL算法進(jìn)行求解花費(fèi)的時(shí)長(zhǎng)，從而驗(yàn)證了DSOL算法在數(shù)據(jù)鏈站點(diǎn)優(yōu)化選址中的有效性。

4 結(jié)論

本文通過(guò)對(duì)數(shù)據(jù)鏈站點(diǎn)選址問(wèn)題進(jìn)行分析，綜合考慮地理高程信息對(duì)電磁信號(hào)覆蓋范圍的影響以及特定標(biāo)志點(diǎn)等因素，建立數(shù)據(jù)鏈站點(diǎn)優(yōu)化選址模型；采用柵格化方法對(duì)數(shù)據(jù)鏈站點(diǎn)布設(shè)區(qū)域進(jìn)行劃分，并結(jié)合廣度優(yōu)先搜索算法的特點(diǎn)，提出了一種數(shù)據(jù)鏈站點(diǎn)選址算法DSOL，算法中引入覆蓋矩陣、判別矩陣、距離矩陣，可以快速尋找數(shù)據(jù)鏈站點(diǎn)最優(yōu)布設(shè)方案。通過(guò)與利用Lingo軟件優(yōu)化數(shù)據(jù)鏈站點(diǎn)選址進(jìn)行對(duì)比仿真實(shí)驗(yàn)，仿真結(jié)果驗(yàn)證了DSOL算法的正確性和有效性。