段宗皓，司賀兵，劉 占

1. 中國(guó)人民公安大學(xué) 研究生院，北京 100038；2. 中國(guó)人民警察大學(xué) 智慧警務(wù)學(xué)院，河北 廊坊 065000

1 研究?jī)?nèi)容

穩(wěn)定通暢的通信網(wǎng)絡(luò)不僅可以提高軍事通信的安全性，也會(huì)增加部隊(duì)作戰(zhàn)的協(xié)同性與機(jī)動(dòng)性，在軍事戰(zhàn)爭(zhēng)中，擁有先進(jìn)通信網(wǎng)絡(luò)技術(shù)的一方往往能占據(jù)戰(zhàn)爭(zhēng)的主動(dòng)性，引導(dǎo)戰(zhàn)爭(zhēng)走向。同時(shí)通信設(shè)施也是現(xiàn)代戰(zhàn)爭(zhēng)中最先被攻擊對(duì)象之一，其一旦被破壞往往造成通信網(wǎng)絡(luò)中斷，使各節(jié)點(diǎn)成為孤立的“聾子”“瞎子”，處于被動(dòng)境地，喪失戰(zhàn)場(chǎng)主動(dòng)性。本文針對(duì)假定的軍事戰(zhàn)備過程，構(gòu)建以139 個(gè)大中型城市為節(jié)點(diǎn)的有線通信網(wǎng)絡(luò)。假定在每個(gè)城市設(shè)置一個(gè)網(wǎng)絡(luò)設(shè)備進(jìn)行專用網(wǎng)絡(luò)連接，城市與城市之間的通信線路以最短距離方式連接，這是解決最短網(wǎng)絡(luò)連接與修復(fù)線路問題的關(guān)鍵。本文主要研究如下4個(gè)問題。

問題1：按照通信線路總長(zhǎng)度最短的連接方案要求，計(jì)算出我國(guó)139 個(gè)城市網(wǎng)絡(luò)連接方案。問題2：假定戰(zhàn)爭(zhēng)期間通信網(wǎng)絡(luò)中的某個(gè)城市節(jié)點(diǎn)被攻擊，并會(huì)破壞通信網(wǎng)絡(luò)的整體連通性，且被攻擊城市節(jié)點(diǎn)遭到的破壞短時(shí)間內(nèi)無法修復(fù)，整個(gè)連通網(wǎng)絡(luò)被分解成具有局部連通性的多個(gè)獨(dú)立分支。為恢復(fù)網(wǎng)絡(luò)的整體連通性，需要啟用預(yù)先在139 個(gè)城市之外設(shè)置的戰(zhàn)備節(jié)點(diǎn)。戰(zhàn)備節(jié)點(diǎn)設(shè)置需與被破壞節(jié)點(diǎn)城市距離最近，且啟動(dòng)戰(zhàn)備節(jié)點(diǎn)后，可形成新的與整個(gè)通信網(wǎng)絡(luò)連通的分支，從而恢復(fù)通信網(wǎng)絡(luò)的整體連通性能。假設(shè)北京、武漢、上海3 個(gè)城市遭到破壞，設(shè)計(jì)給出戰(zhàn)備節(jié)點(diǎn)數(shù)量、地理坐標(biāo)，以及修復(fù)線路的連接方式。問題3：假定武漢、黃石、岳陽(yáng)、沙市、宜昌、信陽(yáng)、南昌、九江、安慶等9 個(gè)城市節(jié)點(diǎn)被同時(shí)摧毀，設(shè)計(jì)給出戰(zhàn)備節(jié)點(diǎn)的數(shù)量及地理坐標(biāo)，同時(shí)提出衡量城市節(jié)點(diǎn)網(wǎng)絡(luò)連通性能評(píng)價(jià)方法。問題4：分析網(wǎng)絡(luò)線路總長(zhǎng)度最短要求下網(wǎng)絡(luò)連通性差和抗攻擊能力弱的問題。通過增加城市節(jié)點(diǎn)間連通線路提高網(wǎng)絡(luò)連通性，其相關(guān)成本也將大大提高。所以，在通信線路總長(zhǎng)度最短的基礎(chǔ)上，城市的通信網(wǎng)絡(luò)應(yīng)具備更優(yōu)良的特點(diǎn)，尤其是要確保一些重要的城市高質(zhì)量連通，要在同時(shí)滿足網(wǎng)絡(luò)經(jīng)濟(jì)性與抗攻擊性的基礎(chǔ)上規(guī)劃最優(yōu)方案。

2 對(duì)研究問題的分析

2.1 問題1的分析

地球是球體，對(duì)于問題1 首先要將城市節(jié)點(diǎn)地理坐標(biāo)轉(zhuǎn)化為球面距離，這樣問題1 就轉(zhuǎn)化為圖論問題。將139個(gè)城市看作139個(gè)節(jié)點(diǎn)，假定任意兩個(gè)節(jié)點(diǎn)都有邊連接，連接邊不區(qū)分方向，設(shè)定每條連接邊的權(quán)值是其兩個(gè)節(jié)點(diǎn)的球面距離，從而構(gòu)成一個(gè)無向完全帶權(quán)圖，即任意兩節(jié)點(diǎn)間都有邊連接，每條邊都有對(duì)應(yīng)權(quán)值。連接139 個(gè)節(jié)點(diǎn)通信線路總長(zhǎng)度最短的網(wǎng)絡(luò)連接方案，轉(zhuǎn)化為求這個(gè)無向完全帶權(quán)圖的最小連通圖。在無向圖中，從某個(gè)節(jié)點(diǎn)到另外一個(gè)節(jié)點(diǎn)之間有路徑相連，稱兩個(gè)節(jié)點(diǎn)為連通的。當(dāng)圖中任意兩節(jié)點(diǎn)間都至少有一條路徑相連稱為連通圖。當(dāng)構(gòu)成連通圖的邊權(quán)值之和最小時(shí)，稱為圖的最小連通圖［1］。問題1 中節(jié)點(diǎn)城市之間通信線路總長(zhǎng)度最短連接方案，即圖的最小連通圖。

構(gòu)建無向完全帶權(quán)圖最小連通圖常用方法有Prim 算法［2］和Kruskal 算法［3］。Prim 算法構(gòu)建具有最小權(quán)值且連接所有節(jié)點(diǎn)的圖，生成圖中沒有回路。其做法為：先以一個(gè)節(jié)點(diǎn)作為最小連通圖的初始節(jié)點(diǎn)，然后以迭代的方式找出最小連通圖與其他節(jié)點(diǎn)權(quán)值最小的邊，將其加入生成圖中；如產(chǎn)生回路則跳過這條邊，繼續(xù)下一節(jié)點(diǎn)。當(dāng)所有節(jié)點(diǎn)都加入生成圖后，就找出了給定圖的最小連通圖。Kruskal 算法在查找最小連通圖之前，先對(duì)所有連接邊按權(quán)值從小到大排序。將排好序的權(quán)值邊依次加入生成圖中，如果加入時(shí)產(chǎn)生回路就跳過該邊，繼續(xù)加入下一條邊。當(dāng)所有節(jié)點(diǎn)都加入生成圖后，就找出了給定圖的最小連通圖。

Kruskal 算法需要對(duì)權(quán)重邊進(jìn)行排序，從最小權(quán)值邊開始構(gòu)建最小連通圖。而Prim算法可從任意節(jié)點(diǎn)開始構(gòu)建最小連通圖，將所有節(jié)點(diǎn)逐一加入生成圖。Prim算法和Kruskal算法的時(shí)間復(fù)雜度分別為O（n2）和O（eloge）（n為節(jié)點(diǎn)數(shù)量，e為連接邊數(shù)量）。Prim 算法時(shí)間復(fù)雜度與圖中邊的數(shù)量無較大關(guān)系，適合稠密圖構(gòu)建最小連通圖；而Kruska 算法需要對(duì)圖的邊進(jìn)行訪問，它的時(shí)間復(fù)雜度取決于圖中邊的數(shù)量，更適合稀疏圖。本文從無向完全圖基礎(chǔ)上構(gòu)建最小連通圖，為稠密圖，連接邊數(shù)量多，因此，采用Prim算法構(gòu)建城市節(jié)點(diǎn)的最小連通圖。

2.2 問題2的分析

該問題中假定3 個(gè)城市節(jié)點(diǎn)分別遭到破壞，不能提供正常網(wǎng)絡(luò)連接功能，導(dǎo)致原本連通的網(wǎng)絡(luò)被分割為多個(gè)連通子圖。此時(shí)需要根據(jù)被破壞節(jié)點(diǎn)關(guān)鍵重要程度和剩余節(jié)點(diǎn)連通情況對(duì)網(wǎng)絡(luò)進(jìn)行修復(fù)，以最大限度保障網(wǎng)絡(luò)正常運(yùn)轉(zhuǎn)。對(duì)于未受損節(jié)點(diǎn)，設(shè)置戰(zhàn)備節(jié)點(diǎn)與其中某個(gè)距離最近的節(jié)點(diǎn)相連接即可。對(duì)需要多個(gè)戰(zhàn)備節(jié)點(diǎn)情況，則需根據(jù)剩余節(jié)點(diǎn)連通情況考慮戰(zhàn)備節(jié)點(diǎn)的個(gè)數(shù)和位置。確定連通子圖數(shù)量，可以分為三種情況：（1）如果連通子圖數(shù)量為1，可以不用設(shè)置戰(zhàn)備節(jié)點(diǎn)，其余節(jié)點(diǎn)仍保持連接；（2）如果連通子圖數(shù)量為2，兩個(gè)連通子圖最近節(jié)點(diǎn)直接連接即可保持連接；（3）如果連通子圖數(shù)量大于2，需設(shè)置戰(zhàn)備節(jié)點(diǎn)，確保戰(zhàn)備節(jié)點(diǎn)到達(dá)連通子圖的距離和最小。

新增加的戰(zhàn)備節(jié)點(diǎn)是在已有連通子圖繼續(xù)保持連通情況下，使所有節(jié)點(diǎn)能夠全連通的最小代價(jià)方案，且不影響已有連通子圖的連接。即在139 個(gè)城市節(jié)點(diǎn)之外的所有坐標(biāo)中選擇能夠使其構(gòu)成全連通的最小代價(jià)總和坐標(biāo)方案。設(shè)置的戰(zhàn)備節(jié)點(diǎn)數(shù)量越多計(jì)算越復(fù)雜，戰(zhàn)備節(jié)點(diǎn)數(shù)量越大，需要計(jì)算的戰(zhàn)備節(jié)點(diǎn)與各連通子圖的距離總和就會(huì)越大，計(jì)算代價(jià)越大。同時(shí)，被破壞的城市若是特別重要的城市節(jié)點(diǎn)，如北京、上海等，需要考慮增設(shè)戰(zhàn)備節(jié)點(diǎn)以承接其關(guān)鍵節(jié)點(diǎn)功能。

2.3 問題3的分析

與問題2相比，問題3在假定被破壞城市節(jié)點(diǎn)數(shù)量和程度上有所不同。問題2 中假定某一個(gè)城市節(jié)點(diǎn)遭到嚴(yán)重破壞，問題3中假定9個(gè)城市節(jié)點(diǎn)被同時(shí)摧毀。若采用與問題2 同樣方式解決問題3，隨著不連通子網(wǎng)數(shù)量的增加，程序計(jì)算時(shí)間復(fù)雜度增加，搜索時(shí)間變長(zhǎng)。因此，尋找收斂速度更快的算法十分必要［1］。本文構(gòu)建了以平均連通度（Cˉ）［4］、連通總距離（L）［5］和節(jié)點(diǎn)關(guān)鍵性（k）三項(xiàng)指標(biāo)為依據(jù)的通信網(wǎng)絡(luò)綜合評(píng)價(jià)指標(biāo)，衡量通信網(wǎng)絡(luò)的連通效率。

2.3.1 平均連通度

在城市節(jié)點(diǎn)無向圖中，與節(jié)點(diǎn)i相連接的連接邊數(shù)量稱為該節(jié)點(diǎn)的連通度，記為ci，連通度反映了節(jié)點(diǎn)與其他節(jié)點(diǎn)連通程度。連通度值越大，節(jié)點(diǎn)與其他節(jié)點(diǎn)連通路徑數(shù)量越多。圖中所有節(jié)點(diǎn)連通度的平均值，稱為圖的平均連通度，記為Cˉ，其計(jì)算見公式（1）。

式中：n為城市節(jié)點(diǎn)數(shù)量。平均連通度值越大，節(jié)點(diǎn)間相連接的路徑就越多，網(wǎng)絡(luò)的整體穩(wěn)定性就越強(qiáng)，同時(shí)網(wǎng)絡(luò)建設(shè)的投入也越大。

2.3.2 連通總距離

網(wǎng)絡(luò)中所有連通節(jié)點(diǎn)之間的距離總和，稱為連通總距離，記為L(zhǎng)，其計(jì)算見公式（2）。在城市節(jié)點(diǎn)對(duì)（vi，vj）（i≠j）之間存在直接路徑連通時(shí)，才計(jì)入連通總距離，間接連通的節(jié)點(diǎn)間距離不計(jì)入連通總距離。

式中：dij為城市節(jié)點(diǎn)i與城市節(jié)點(diǎn)j之間的直接連通路徑距離（無向圖中重復(fù)邊只計(jì)算1 次）。連通總距離反映了城市通信節(jié)點(diǎn)網(wǎng)絡(luò)建設(shè)總投入，總距離越大，對(duì)應(yīng)的網(wǎng)絡(luò)建設(shè)投入就越多。

2.3.3 節(jié)點(diǎn)關(guān)鍵性

每個(gè)城市節(jié)點(diǎn)的連通性對(duì)整個(gè)城市節(jié)點(diǎn)網(wǎng)絡(luò)連通重要性并不相同。與多個(gè)節(jié)點(diǎn)城市相連接的節(jié)點(diǎn)，可以被視為局部網(wǎng)絡(luò)中樞，一旦其節(jié)點(diǎn)功能被破壞，會(huì)造成多個(gè)城市節(jié)點(diǎn)網(wǎng)絡(luò)通信故障。對(duì)于首都、省會(huì)等大城市節(jié)點(diǎn)，其節(jié)點(diǎn)功能一旦被破壞，除引發(fā)整體網(wǎng)絡(luò)通信故障外，還會(huì)帶來更大負(fù)面影響，此類節(jié)點(diǎn)關(guān)鍵性值要高于一般小城市。

節(jié)點(diǎn)關(guān)鍵性是根據(jù)節(jié)點(diǎn)地理位置、節(jié)點(diǎn)在網(wǎng)絡(luò)中的關(guān)連節(jié)點(diǎn)數(shù)量、城市規(guī)模等因素綜合給出的評(píng)價(jià)指標(biāo)。計(jì)算整體網(wǎng)絡(luò)綜合性時(shí)，節(jié)點(diǎn)關(guān)鍵性參數(shù)可設(shè)置為1。

本文綜合平均連通度、連通總距離和節(jié)點(diǎn)關(guān)鍵性等因素，綜合評(píng)價(jià)通信網(wǎng)絡(luò)連通性能，特別在城市節(jié)點(diǎn)被破壞情況下，對(duì)重建節(jié)點(diǎn)、備用節(jié)點(diǎn)選擇提供參考。通信網(wǎng)絡(luò)綜合評(píng)價(jià)指標(biāo)反映了網(wǎng)絡(luò)整體連通性能和效率，對(duì)通信網(wǎng)絡(luò)評(píng)價(jià)和網(wǎng)絡(luò)可靠性都提出了要求。

2.4 問題4的分析

在構(gòu)建通信網(wǎng)絡(luò)的過程中，如果單純追求網(wǎng)絡(luò)線路總長(zhǎng)度最短，容易導(dǎo)致網(wǎng)絡(luò)的抗攻擊能力減弱，而提高網(wǎng)絡(luò)抵抗攻擊能力往往又意味著增加網(wǎng)絡(luò)建設(shè)經(jīng)濟(jì)成本。在問題1 構(gòu)造的通信網(wǎng)絡(luò)最小連通圖基礎(chǔ)上，構(gòu)建連通性能更高、抗攻擊性能更優(yōu)的網(wǎng)絡(luò)非常必要，尤其是對(duì)一些重要城市節(jié)點(diǎn)，需要確保其在通信網(wǎng)絡(luò)中保持持續(xù)連通。因此，設(shè)計(jì)方案在考慮網(wǎng)絡(luò)抗毀性、可靠性、通信能力等約束的同時(shí)，還需要考慮網(wǎng)絡(luò)重建的經(jīng)濟(jì)性和可行性等約束。連通性約束指復(fù)雜信息網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)改變后，任意節(jié)點(diǎn)之間至少存在一條路徑相連，這是網(wǎng)絡(luò)連通的最低要求。本文對(duì)通信網(wǎng)絡(luò)中的重要城市節(jié)點(diǎn)，如首都、直轄市和省會(huì)城市，采取預(yù)先戰(zhàn)備節(jié)點(diǎn)設(shè)置策略，一旦遭受攻擊可以將節(jié)點(diǎn)功能切換到戰(zhàn)備節(jié)點(diǎn)，確保通信網(wǎng)絡(luò)的連通性能。

3 問題的解決方案

3.1 問題1模型建立與求解

3.1.1 地理坐標(biāo)的轉(zhuǎn)化

通過城市間的地理坐標(biāo)計(jì)算出地球上這兩個(gè)城市節(jié)點(diǎn)所在位置大圓的劣弧長(zhǎng)［6-7］LAB，假設(shè)地球?yàn)榍蝮w且半徑為R，而A、B的地理坐標(biāo)分別為A（JA，WA）、B（JB，WB）。如圖1 所示球體，O 為球心，C 與A 緯度相同，C 與B 經(jīng)度相同，F(xiàn) 為BC 延長(zhǎng)線與過球心直線的交點(diǎn)，CH與BE都垂直于OF，BD垂直于CH。由此可以推導(dǎo)出AB間距離，見公式（3）。

圖1 地球的球面模型

采用總長(zhǎng)度最短的方案連接139 個(gè)節(jié)點(diǎn)之間的通信線路，本質(zhì)上就是求139 個(gè)節(jié)點(diǎn)的最小連通圖，與平面圖形最小連通圖的差別在于球體上根據(jù)經(jīng)緯度設(shè)置每個(gè)節(jié)點(diǎn)坐標(biāo)，球體兩點(diǎn)距離根據(jù)兩點(diǎn)經(jīng)緯坐標(biāo)計(jì)算劣弧長(zhǎng)。球體上點(diǎn)與點(diǎn)之間距離需要單獨(dú)計(jì)算和處理。

3.1.2 最小連通圖生成模型的建立

計(jì)算每個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的距離（任意兩個(gè)節(jié)點(diǎn)都可建立通信線路），利用Prim算法構(gòu)建最小連通圖［8］。算法描述：（1）城市節(jié)點(diǎn)集合V1，帶權(quán)無向邊集合E1，其邊權(quán)值為城市節(jié)點(diǎn)之間的坐標(biāo)距離，集合V2存放生成的最小連通圖節(jié)點(diǎn)，集合E2存放生成的最小連通圖的邊。（2）從V1中選取節(jié)點(diǎn)x，將x加入V2中，此時(shí)V2=｛x｝，以x作為最小連通圖起始節(jié)點(diǎn)，由該節(jié)點(diǎn)開始構(gòu)建最小連通圖；集合E2初始為空。（3）在集合E1中，選取V1中節(jié)點(diǎn)到V2中節(jié)點(diǎn)權(quán)值最小的連接邊（u，v），v在V2中、u在V1中；將u加入V2，同時(shí)將u從V1中刪除，并將（u，v）加入邊集合E2。重復(fù)操作此步驟，直到集合V1中節(jié)點(diǎn)全部添加到V2中。（4）E2即為集合V1中城市節(jié)點(diǎn)的最小連通圖，其各節(jié)點(diǎn)之間的距離總和最小。

構(gòu)建的總長(zhǎng)度最短連接方案：（阿克蘇，喀什）；（喀什，和田）；（阿克蘇，塔城）；（塔城，阿勒泰）；（阿勒泰，烏魯木齊）；（烏魯木齊，哈密）……（呼和浩特，二連浩特）；（二連浩特，錫林浩特）；（齊齊哈爾，海拉爾）；（海拉爾，滿洲里）；（齊齊哈爾，黑河）；（格爾木，拉薩）；（拉薩，日喀則）。連接139 個(gè)節(jié)點(diǎn)通信線路總長(zhǎng)度最短的網(wǎng)絡(luò)連接方案如圖2所示。

圖2 城市節(jié)點(diǎn)最小連通圖連接方案

3.2 問題2求解方案與討論

假定北京、武漢和上海3 個(gè)城市節(jié)點(diǎn)分別遭到破壞，討論如下：

3.2.1 假定上海節(jié)點(diǎn)被破壞

圖3 所示為假定上海節(jié)點(diǎn)遭到破壞后的連通圖，該節(jié)點(diǎn)遭到破壞后連通子圖數(shù)量為1。此種情況下，除被破壞節(jié)點(diǎn)外，整個(gè)網(wǎng)絡(luò)仍然連通?？紤]上海節(jié)點(diǎn)的重要性，需在距離上海節(jié)點(diǎn)最近位置選取戰(zhàn)備節(jié)點(diǎn)，將上海節(jié)點(diǎn)功能轉(zhuǎn)移到該戰(zhàn)備節(jié)點(diǎn)即可，無需改動(dòng)其余節(jié)點(diǎn)連接狀態(tài)。

圖3 假定上海節(jié)點(diǎn)被破壞后的連通圖

3.2.2 假定武漢節(jié)點(diǎn)被破壞

圖4 所示為假定武漢節(jié)點(diǎn)遭到破壞后的連通圖情況，武漢節(jié)點(diǎn)遭到破壞后連通子圖數(shù)量為2，連通網(wǎng)絡(luò)被分割為兩個(gè)互不連通的子網(wǎng)，因此，需要選擇新的戰(zhàn)備節(jié)點(diǎn)并修復(fù)網(wǎng)絡(luò)，從而使整個(gè)網(wǎng)絡(luò)連通。經(jīng)檢索得到兩個(gè)不連通子圖中距離最近城市節(jié)點(diǎn)為（營(yíng)口，大連），計(jì)算距離為203 km（給定坐標(biāo)點(diǎn)間球面距離，下同），連通這兩個(gè)城市節(jié)點(diǎn)可以在最小距離代價(jià)下重新連通整個(gè)網(wǎng)絡(luò)。但由于武漢節(jié)點(diǎn)地理位置重要，該節(jié)點(diǎn)功能不能廢棄，因此，需要在該節(jié)點(diǎn)附近位置選擇戰(zhàn)備節(jié)點(diǎn)，并將該節(jié)點(diǎn)功能轉(zhuǎn)移至戰(zhàn)備節(jié)點(diǎn)。

圖4 假定武漢節(jié)點(diǎn)破壞后的連通圖

連通子圖1（圖4 中藍(lán)色部分）中距離武漢較近的城市節(jié)點(diǎn)為黃石（83 km），連通子圖2（圖4 中紅色部分）中距離武漢較近的城市節(jié)點(diǎn)為信陽(yáng)（174 km）、岳陽(yáng)（177 km），同時(shí)黃石距離岳陽(yáng)（206 km）較信陽(yáng)（235 km）更近一些。為便于將武漢節(jié)點(diǎn)功能轉(zhuǎn)移到戰(zhàn)備節(jié)點(diǎn)，選取黃石作為連接點(diǎn)之一，連接（黃石，岳陽(yáng)）兩個(gè)節(jié)點(diǎn)，并選取武漢到兩節(jié)點(diǎn)連線的垂足為戰(zhàn)備節(jié)點(diǎn)，計(jì)算得到戰(zhàn)備節(jié)點(diǎn)坐標(biāo)為（114.72，30.08），如圖5所示。

圖5 啟用（黃石，岳陽(yáng)）后連通圖

3.2.3 假定北京節(jié)點(diǎn)被破壞

圖6 所示為假定北京節(jié)點(diǎn)遭到破壞后的連通圖情況，北京節(jié)點(diǎn)遭到破壞后連通子圖數(shù)量為3，連通網(wǎng)絡(luò)被分割為3 個(gè)互不連通子網(wǎng)。結(jié)合前面對(duì)問題2 的分析，連通子圖數(shù)量大于2，需要設(shè)置戰(zhàn)備節(jié)點(diǎn)，并且需要確保戰(zhàn)備節(jié)點(diǎn)到達(dá)連通子圖的距離和最小。戰(zhàn)備節(jié)點(diǎn)是在不影響已有連通子圖的連接狀態(tài)，同時(shí)使已有連通子圖不間斷持續(xù)工作情況下，滿足所有節(jié)點(diǎn)全連通的最小代價(jià)方案。需要在139 個(gè)城市節(jié)點(diǎn)之外的所有坐標(biāo)中選擇能夠使其全連通的最小代價(jià)總和坐標(biāo)方案。設(shè)置的戰(zhàn)備節(jié)點(diǎn)數(shù)量越多，計(jì)算就越復(fù)雜。

圖6 假定北京節(jié)點(diǎn)破壞后的連通圖

如圖6 所示，北京節(jié)點(diǎn)遭到嚴(yán)重破壞時(shí)原來的連通圖被分成3 個(gè)連通子圖。經(jīng)檢索得到不連通子圖中最近距離的3 個(gè)城市節(jié)點(diǎn)為天津、保定、張家口，其中（天津，保定）距離152 km，（保定，張家口）距離217 km，（天津，張家口）距離271 km。為保證所有正常運(yùn)行城市節(jié)點(diǎn)網(wǎng)絡(luò)的全連通，需要將3 個(gè)不連通的子網(wǎng)絡(luò)進(jìn)行連通。同時(shí)，考慮假定節(jié)點(diǎn)功能的重要性，需將其相關(guān)節(jié)點(diǎn)功能進(jìn)行轉(zhuǎn)移。在（天津，保定，張家口）三節(jié)點(diǎn)組成三角形的費(fèi)馬點(diǎn)設(shè)置戰(zhàn)備節(jié)點(diǎn)，可滿足最小開銷實(shí)現(xiàn)網(wǎng)絡(luò)的全連通。計(jì)算得到該戰(zhàn)備節(jié)點(diǎn)的坐標(biāo)為（115.79，39.22），該戰(zhàn)備節(jié)點(diǎn)與天津距離122 km，與保定距離48 km，與張家口距離188 km，與功能被轉(zhuǎn)移節(jié)點(diǎn)北京距離92 km，如圖7所示。

圖7 啟用戰(zhàn)備節(jié)點(diǎn)后的連通圖

3.3 問題3求解方案與討論

3.3.1 假定多個(gè)節(jié)點(diǎn)被摧毀的戰(zhàn)備節(jié)點(diǎn)

如果多個(gè)城市節(jié)點(diǎn)通信功能被摧毀，通信網(wǎng)絡(luò)被分割為多個(gè)相互不連通子網(wǎng)，被摧毀的城市節(jié)點(diǎn)通信功能不能正常運(yùn)轉(zhuǎn)，相互不連通的子網(wǎng)間通信功能不能正常運(yùn)轉(zhuǎn)。此時(shí)，需要確定連通子網(wǎng)數(shù)量，采取非連通圖中距離最近點(diǎn)連接，以保證網(wǎng)絡(luò)連通。假定武漢、黃石、岳陽(yáng)、沙市、宜昌、信陽(yáng)、南昌、九江和安慶9 個(gè)城市節(jié)點(diǎn)功能同時(shí)被損毀，如圖8 所示，連通網(wǎng)絡(luò)被分割為5個(gè)獨(dú)立的連通子圖。

圖8 假定武漢等9個(gè)城市節(jié)點(diǎn)破壞后的連通圖

5 個(gè)不連通子網(wǎng)距離最近的5 個(gè)節(jié)點(diǎn)為襄樊（112.12，32.01）、長(zhǎng)沙（112.94，28.23）、合肥（117.23，31.82）、常德（111.7，29.03）、景德鎮(zhèn)（117.18，29.27），這些節(jié)點(diǎn)分布在被摧毀的9 個(gè)城市節(jié)點(diǎn)附近?？紤]戰(zhàn)備節(jié)點(diǎn)建設(shè)經(jīng)濟(jì)性，只討論1個(gè)或2個(gè)戰(zhàn)備節(jié)點(diǎn)情況。

如果僅設(shè)置1 個(gè)戰(zhàn)備節(jié)點(diǎn)，則該節(jié)點(diǎn)需遵循到5個(gè)待連通節(jié)點(diǎn)的距離和最小原則，在上述5 個(gè)待連通節(jié)點(diǎn)區(qū)域進(jìn)行檢索，得到節(jié)點(diǎn)（113.66，29.75）符合要求，經(jīng)計(jì)算該節(jié)點(diǎn)到達(dá)上述5 個(gè)城市節(jié)點(diǎn)連接總長(zhǎng)為1 437.9 km。

如果設(shè)置2個(gè)戰(zhàn)備節(jié)點(diǎn)，則采用戰(zhàn)備節(jié)點(diǎn)1連接上述5 個(gè)城市節(jié)點(diǎn)中的3 個(gè)，戰(zhàn)備節(jié)點(diǎn)2 連接另外兩個(gè)，此外還需兩個(gè)戰(zhàn)備節(jié)點(diǎn)之間相連接，同時(shí)需遵循距離和最小原則。戰(zhàn)備節(jié)點(diǎn)1 設(shè)置時(shí)通過兩條兩城市節(jié)點(diǎn)連線垂直平分線交點(diǎn)進(jìn)行確定，戰(zhàn)備節(jié)點(diǎn)2設(shè)置則遵循距離戰(zhàn)備節(jié)點(diǎn)1 和另外兩城市節(jié)點(diǎn)連線距離最小原則進(jìn)行確定。經(jīng)計(jì)算和檢索，得到戰(zhàn)備節(jié)點(diǎn)1 坐標(biāo)（113.40，30.31），戰(zhàn)備節(jié)點(diǎn)2 坐標(biāo)（116.35，30.43），連接總長(zhǎng)為1 290.2 km。

此外，設(shè)置1 個(gè)戰(zhàn)備節(jié)點(diǎn)情況下，增加節(jié)點(diǎn)數(shù)量1，連通后增加總連通度為10，計(jì)算得到連通網(wǎng)絡(luò)的總平均度值為1.98。設(shè)置2 個(gè)戰(zhàn)備節(jié)點(diǎn)情況下，增加節(jié)點(diǎn)數(shù)量2，連通后增加總連通度11，計(jì)算得到連通網(wǎng)絡(luò)的總平均度值為1.97。若僅增加1 個(gè)戰(zhàn)備節(jié)點(diǎn)，該節(jié)點(diǎn)連接節(jié)點(diǎn)過多，一旦再被破壞，將造成網(wǎng)絡(luò)更大損失。增加2 個(gè)戰(zhàn)備節(jié)點(diǎn)可以減少節(jié)點(diǎn)城市連接負(fù)載，降低網(wǎng)絡(luò)風(fēng)險(xiǎn)，并可以滿足將周邊被破壞城市節(jié)點(diǎn)功能向戰(zhàn)備節(jié)點(diǎn)轉(zhuǎn)移的要求。綜合以上考慮，在此種情況下，選擇增加2個(gè)戰(zhàn)備節(jié)點(diǎn)的策略。

3.3.2 通信網(wǎng)絡(luò)綜合評(píng)價(jià)指標(biāo)

網(wǎng)絡(luò)連通性指標(biāo)一般有連通度、通達(dá)度、回路數(shù)等［9-11］，在本文所研究的節(jié)點(diǎn)城市通信網(wǎng)絡(luò)中，特別是有節(jié)點(diǎn)被破壞后的重建網(wǎng)絡(luò)設(shè)計(jì)方案中，衡量網(wǎng)絡(luò)方案優(yōu)劣不能簡(jiǎn)單以連通與否作為標(biāo)準(zhǔn)，還要考慮城市節(jié)點(diǎn)關(guān)鍵性、通信網(wǎng)絡(luò)建設(shè)投入最優(yōu)等具體情況［12］。對(duì)于關(guān)鍵城市需要設(shè)置戰(zhàn)備節(jié)點(diǎn)，對(duì)于一般節(jié)點(diǎn)需要考慮重建時(shí)效，能在最短時(shí)間內(nèi)恢復(fù)重建保障網(wǎng)絡(luò)整體通信暢通。本文在確保城市節(jié)點(diǎn)網(wǎng)絡(luò)最小連通圖正常通信前提下，提出以平均連通度、連通總距離和節(jié)點(diǎn)關(guān)鍵性為參考因素的通信網(wǎng)絡(luò)綜合評(píng)價(jià)指標(biāo)，用于更優(yōu)的網(wǎng)絡(luò)建設(shè)方案評(píng)價(jià)，見公式（4）。

式中：p代表綜合評(píng)價(jià)指標(biāo)；k為節(jié)點(diǎn)關(guān)鍵性指標(biāo)，反映節(jié)點(diǎn)城市關(guān)鍵重要性，首都、省會(huì)等大城市的關(guān)鍵性值要高于一般小城市；Cˉ為城市節(jié)點(diǎn)網(wǎng)絡(luò)的平均連通度，反映整體網(wǎng)絡(luò)的連通復(fù)雜程度，在整體網(wǎng)絡(luò)連通情況下，Cˉ值越高，網(wǎng)絡(luò)連通越復(fù)雜；L為連通總距離，是網(wǎng)絡(luò)中所有連通節(jié)點(diǎn)之間的距離總和。

在本文構(gòu)建的城市通信網(wǎng)絡(luò)中，節(jié)點(diǎn)的連通度越大，表明能與其直接通信的節(jié)點(diǎn)越多，而該節(jié)點(diǎn)一旦被破壞帶來的網(wǎng)絡(luò)中斷則越嚴(yán)重，所以，將平均連通度作為反相關(guān)指數(shù)之一。連通總距離越大，則表明連通網(wǎng)絡(luò)線路越長(zhǎng)，需付出相應(yīng)建設(shè)費(fèi)用越高。從經(jīng)濟(jì)角度考慮，將連通總距離作為反相關(guān)指數(shù)之一。節(jié)點(diǎn)關(guān)鍵性體現(xiàn)的是節(jié)點(diǎn)城市在經(jīng)濟(jì)、軍事等方面的重要程度。首都、省會(huì)或人口超千萬的大城市，或者處于經(jīng)濟(jì)、軍事關(guān)鍵地域的城市，在整個(gè)連通網(wǎng)絡(luò)中除連通節(jié)點(diǎn)功能外，還擔(dān)負(fù)其他重要功能，k值較大。節(jié)點(diǎn)關(guān)鍵性高的城市節(jié)點(diǎn)一旦被破壞，需要在其周圍建立戰(zhàn)備節(jié)點(diǎn)，并將城市節(jié)點(diǎn)功能向戰(zhàn)備節(jié)點(diǎn)轉(zhuǎn)移。

3.4 問題4模型建立與討論

在構(gòu)建通信網(wǎng)絡(luò)的過程中，不能一味追求網(wǎng)絡(luò)線路總長(zhǎng)度最短，還需考慮網(wǎng)絡(luò)的連通性和抗攻擊能力，而提高連通性往往意味著網(wǎng)絡(luò)構(gòu)建的經(jīng)濟(jì)成本增加。本文提出的綜合評(píng)價(jià)指標(biāo)既考慮構(gòu)建網(wǎng)絡(luò)的經(jīng)濟(jì)性，又考慮網(wǎng)絡(luò)的抗攻擊性。網(wǎng)絡(luò)結(jié)構(gòu)的微小不同都會(huì)引起網(wǎng)絡(luò)連通度的不同，連通度主要由網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)決定，它取決于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的以下因素：（1）對(duì)既有網(wǎng)絡(luò)添加邊，會(huì)增加網(wǎng)絡(luò)的連通度；（2）兩個(gè)相同節(jié)點(diǎn)數(shù)和邊數(shù)的網(wǎng)絡(luò)，其連通度會(huì)因?yàn)檫叺奈恢貌煌煌?，此處邊的位置指邊的鄰接?jié)點(diǎn)。在通信網(wǎng)絡(luò)設(shè)計(jì)中，“加邊”必定會(huì)增加網(wǎng)絡(luò)的連通性，但是邊加在網(wǎng)絡(luò)中的不同位置也會(huì)影響網(wǎng)絡(luò)的連通度。

對(duì)通信網(wǎng)絡(luò)而言，連通度越高，表明節(jié)點(diǎn)與其他節(jié)點(diǎn)連接的邊越多，中心節(jié)點(diǎn)負(fù)載越大，則該節(jié)點(diǎn)被破壞后帶來的網(wǎng)絡(luò)中斷影響越大。因此，通信網(wǎng)絡(luò)設(shè)計(jì)需要采用綜合評(píng)價(jià)指標(biāo)衡量網(wǎng)絡(luò)的連通效率，以及單個(gè)城市節(jié)點(diǎn)在網(wǎng)絡(luò)中的連通性能。特別是在局部節(jié)點(diǎn)出現(xiàn)損毀時(shí)，需要根據(jù)網(wǎng)絡(luò)連通情況調(diào)整或增加戰(zhàn)備節(jié)點(diǎn)，使網(wǎng)絡(luò)以最快速度、最小代價(jià)恢復(fù)連通。

4 結(jié)束語(yǔ)

穩(wěn)定通暢的通信網(wǎng)絡(luò)對(duì)國(guó)家安全和社會(huì)安全至關(guān)重要。本文從構(gòu)建城市通信網(wǎng)絡(luò)入手，利用Prim算法構(gòu)建最小生成網(wǎng)絡(luò)，并對(duì)連通網(wǎng)絡(luò)局部節(jié)點(diǎn)損毀進(jìn)行恢復(fù)連通策略分析和設(shè)計(jì)。若假定的城市節(jié)點(diǎn)被損毀，通信網(wǎng)絡(luò)被分割為多個(gè)不連通網(wǎng)絡(luò)，從最大效率保障整體網(wǎng)絡(luò)通信連通性策略入手，提出網(wǎng)絡(luò)綜合評(píng)價(jià)指標(biāo)策略，綜合網(wǎng)絡(luò)連通度、網(wǎng)絡(luò)連通距離和節(jié)點(diǎn)關(guān)鍵性等因素整體評(píng)估網(wǎng)絡(luò)的效能和戰(zhàn)備節(jié)點(diǎn)構(gòu)建策略。同時(shí)，本研究也存在一些不足，如計(jì)算城市節(jié)點(diǎn)距離采用球面坐標(biāo)計(jì)算，對(duì)多個(gè)城市節(jié)點(diǎn)被破壞僅提出了解決思路和定性分析等，要進(jìn)一步解決這些問題還需后續(xù)深入研究。