保持網(wǎng)絡(luò)連通性的最優(yōu)節(jié)點(diǎn)配置問題

許 珂 ，陸 疌

（1.上海微系統(tǒng)與信息技術(shù)研究所微系統(tǒng)技術(shù)重點(diǎn)實(shí)驗(yàn)室，上海200050；2.上海科技大學(xué)信息科學(xué)與技術(shù)學(xué)院，上海201210；3.中國科學(xué)院大學(xué)北京100049）

無線傳感網(wǎng)絡(luò)，移動(dòng)機(jī)器人網(wǎng)絡(luò)，通信網(wǎng)絡(luò)等協(xié)同網(wǎng)絡(luò)在現(xiàn)在的社會(huì)中有著廣泛的應(yīng)用，例如運(yùn)動(dòng)協(xié)調(diào)[1]，目標(biāo)追蹤[2]，資源分配[3]等。為了滿足絕大多數(shù)的協(xié)同工作，都會(huì)要求網(wǎng)絡(luò)本身能夠保持連通的拓?fù)浣Y(jié)構(gòu)。到目前為止，許多學(xué)者對(duì)網(wǎng)絡(luò)連通性的相關(guān)問題[4-10]展開了廣泛研究。例如，Spanos等人提出幾何連通的魯棒性，提供了多智能網(wǎng)絡(luò)中在保持連通性的情況下，智能體的可移動(dòng)范圍[4]。還有通過建立最大化網(wǎng)絡(luò)的代數(shù)連通度模型（代數(shù)連通度是網(wǎng)絡(luò)對(duì)應(yīng)的Laplace矩陣的第二最小特征值，表示無向網(wǎng)絡(luò)中連通程度）來解決保持網(wǎng)絡(luò)連通性的問題[9-10]。

文中構(gòu)造一個(gè)與上述方式不同的混合整數(shù)模型來解決網(wǎng)絡(luò)連通性的問題。在保持放置節(jié)點(diǎn)的網(wǎng)絡(luò)連通的同時(shí)，要求節(jié)點(diǎn)能夠最優(yōu)配置。

1 最優(yōu)節(jié)點(diǎn)配置問題的實(shí)例

節(jié)點(diǎn)V={1,2,3}可以被放置在如圖一所示的5個(gè)位置上，灰色的線段表示可能存在的邊（當(dāng)且僅當(dāng)該條邊的左右兩個(gè)位置都放置了節(jié)點(diǎn)，該條邊才存在）。為了簡單起見，假設(shè)在這個(gè)例子中，不考慮每個(gè)節(jié)點(diǎn)放置到任一位置上的費(fèi)用，即放置節(jié)點(diǎn)的費(fèi)用都相同，則圖二所表示的即為最優(yōu)節(jié)點(diǎn)配置問題的一個(gè)最優(yōu)解，位置1，2，4在放置節(jié)點(diǎn)后構(gòu)成一個(gè)連通的網(wǎng)絡(luò)。

圖1 節(jié)點(diǎn)配置問題

圖2 節(jié)點(diǎn)配置問題解

2 問題模型

假設(shè)網(wǎng)絡(luò)G={C,E}是連通的（若網(wǎng)絡(luò)不連通，則網(wǎng)絡(luò)可根據(jù)其拓?fù)浣Y(jié)構(gòu)分為兩個(gè)子網(wǎng)絡(luò)，分別在兩個(gè)子網(wǎng)絡(luò)上求解原問題），C={1,2,...,C}表示網(wǎng)絡(luò)中位置的集合，E?C×C即網(wǎng)絡(luò)中位置之間邊的集合。有V個(gè)節(jié)點(diǎn)V={1,2,...,V}和C個(gè)網(wǎng)絡(luò)中的位置C={1,2,...,C}。對(duì)于每一個(gè)節(jié)點(diǎn)v∈V和網(wǎng)絡(luò)中的位置i∈C，定義變量表示當(dāng)節(jié)點(diǎn)v被放置到位置i上時(shí)定義(·)為節(jié)點(diǎn)v被放置到位置i上時(shí)的費(fèi)用函數(shù)。在這里，我們定義一個(gè)子網(wǎng)絡(luò)表示放置節(jié)點(diǎn)的位置構(gòu)成的網(wǎng)絡(luò)，其中即為分配 了 節(jié) 點(diǎn) 的 位 置 的 集 合即為和相關(guān)的邊的集合。

2.1 目標(biāo)函數(shù)

本問題的目標(biāo)是最小化放置節(jié)點(diǎn)到網(wǎng)絡(luò)中位置的費(fèi)用，顯而易見，通過上述對(duì)變量的定義，總費(fèi)用如下：

2.2 函數(shù)約束

本問題的約束可以分為兩個(gè)類型，資源分配約束和網(wǎng)絡(luò)位置連通性約束。

2.2.1 資源配置約束

節(jié)點(diǎn)配置問題實(shí)際上就是資源配置問題的一種變形，因此，它保有常見資源配置問題的約束。

1）每個(gè)節(jié)點(diǎn)只能分配到一個(gè)位置；

2）每個(gè)位置上最多只能放置一個(gè)節(jié)點(diǎn)。

2.2.2 網(wǎng)絡(luò)位置連通性約束

為了保證放置節(jié)點(diǎn)的網(wǎng)絡(luò)可以保持連通性，我們需要增加相應(yīng)的約束。對(duì)于無向圖G={C,E}是連通圖當(dāng)且僅當(dāng)對(duì)于任意的(i,j)∈E,i≠j，存在一條從i到j(luò)的路徑。對(duì)于有向圖G={C,E}是強(qiáng)連通圖當(dāng)且僅當(dāng)對(duì)于任意的有序組合(i,j)∈E,i≠j，存在一條從i到j(luò)的有向路徑。根據(jù)有向圖和無向圖關(guān)于網(wǎng)絡(luò)連通性的定義，我們將此部分約束分為兩類，在下一章節(jié)中詳細(xì)介紹。

2.3 數(shù)學(xué)模型

最優(yōu)節(jié)點(diǎn)配置問題可以被表示為：

s.t.約束（1）（2）

3 子圖的連通性約束

現(xiàn)如今，有很多學(xué)者提出了建立不同的優(yōu)化模型用來解決網(wǎng)絡(luò)連通性問題[11-22]。例如Miller等人提出通過Miller-Tucker-Zemlin約束解決旅行商問題。他們提出的大部分方法是通過解決最小生成樹問題轉(zhuǎn)化為解決網(wǎng)絡(luò)連通性問題。其中，單一商品流約束（Single-Commodity Flow Constraints，SCFC）被Neng Fan等人通過建立混合整數(shù)規(guī)劃模型解決網(wǎng)絡(luò)連通性的問題--連接支配集（Connected Dominating Set）和電力支配集（Power Dominating Set）問題[15]。文中運(yùn)用單一商品流約束來構(gòu)造最優(yōu)節(jié)點(diǎn)配置問題中的連通性約束。

3.1 無向圖的連通性約束

毫無疑問的，如果一個(gè)無向圖是連通的，當(dāng)且僅當(dāng)它包含一棵生成樹。SCFC就是通過構(gòu)造一棵生成樹的方式來保證網(wǎng)絡(luò)的連通性。首先，我們將放置節(jié)點(diǎn)“1”的網(wǎng)絡(luò)位置定義為所構(gòu)造生成樹的根，由根向放置了節(jié)點(diǎn)的其他位置發(fā)出|V|-1個(gè)單位流，流經(jīng)每一個(gè)放置節(jié)點(diǎn)的位置都會(huì)消耗一個(gè)單位流，其他位置不消耗流。為了構(gòu)造這樣的流結(jié)構(gòu)，引入一組輔助變量fij∈R，對(duì)于每一條邊(i,j)∈E，fij是從位置i到j(luò)流經(jīng)的流數(shù)目。

保持連通性的約束如下：

約束（5）確保每條邊上的流是非負(fù)的；約束（6）表示當(dāng)網(wǎng)絡(luò)中位置i，j中有任一位置沒有放置節(jié)點(diǎn)時(shí)，變量fij等于0；而約束（7）保證流入根的流的總和為0；最后，約束（8）確保了每個(gè)位置上流的流入流出是平衡的，如果位置i放置節(jié)點(diǎn)“1”（即為根），那么位置i流入流出流的差值等于1-|V|，如果位置i上放置某一節(jié)點(diǎn)（除了節(jié)點(diǎn)“1”），流入流出的流的差值應(yīng)當(dāng)為-1，其他的情況，流入流出的流的差為0。

所有滿足SCFC約束的最優(yōu)節(jié)點(diǎn)配置問題的可行解都可以保證：每一個(gè)被放置節(jié)點(diǎn)的位置（除了被選中為生成樹根的位置）都會(huì)消耗一個(gè)來自根的單位流，因此網(wǎng)絡(luò)的連通性也可以保障。

考慮到之前節(jié)點(diǎn)配置問題提出的約束（1）-（2），在這個(gè)模型中，總共有|V||C|+||E個(gè)變量和|V|+3|C|+3|E|=O(|V|+|C|+|E|)個(gè)約束，其中整數(shù)變量為|V||C|個(gè)。

3.2 有向圖的連通性約束

在3.1中，對(duì)于無向圖，我們只需要構(gòu)造一個(gè)生成樹來保證網(wǎng)絡(luò)連通性，但在有向圖中，僅僅構(gòu)造一個(gè)生成樹是不能滿足強(qiáng)連通條件的。因此，在單一商品流約束的基礎(chǔ)上，要求每個(gè)放置了節(jié)點(diǎn)的位置都需要作為生成樹的根，構(gòu)造|V|棵對(duì)應(yīng)的生成樹，按照放置節(jié)點(diǎn)的順序分別稱為生成樹1,2,3,...,|V|。

保持連通性的約束如下：

約束（9）是確保放置節(jié)點(diǎn)k∈V的位置作為生成樹k的根時(shí)，每條邊上的流是非負(fù)的；約束（10）表示當(dāng)網(wǎng)絡(luò)中位置i，j中有任一位置沒有放置節(jié)點(diǎn)時(shí)，在構(gòu)造的每一個(gè)生成樹中，流過(i,j)的流為0，即變量等于0；而約束（11）是對(duì)應(yīng)于構(gòu)造的每一棵生成樹k的根，流入根的流的總和為0；最后，約束（12）確保了對(duì)于每一棵生成樹k，每個(gè)位置上流的流入流出是平衡的，如果位置i放置節(jié)點(diǎn)k（即作為生成樹k的根，=1），那么對(duì)于生成樹k有3種情況，一是位置i流入流出流的差等于1-|V|，二是位置i上放置某一節(jié)點(diǎn)（除了節(jié)點(diǎn)k），流入流出流的差值應(yīng)當(dāng)為-1，其他的情況，流入流出的流為0。

考慮到之前節(jié)點(diǎn)配置問題提出的約束（1）-（2），在這個(gè)模型中，總共有|V||C|+|E||V|個(gè)變量和|V|+(1+2|V|)|C|+3|E||V|個(gè)約束，其中，整數(shù)變量為|V||C|。

4 仿真實(shí)驗(yàn)

首先，我們使用現(xiàn)有的優(yōu)化軟件包來仿真驗(yàn)證模型的正確性。仿真環(huán)境是在matlab 2012a。使用傳統(tǒng)的分支界定算法求解該問題，并驗(yàn)證結(jié)果的正確性[23]。

以無向圖對(duì)應(yīng)的模型為例，我們考慮這樣一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)：14個(gè)網(wǎng)絡(luò)位置和6個(gè)節(jié)點(diǎn)，如圖3所示。簡單起見，令費(fèi)用函數(shù)為線性函數(shù)，節(jié)點(diǎn)放置不同位置上對(duì)應(yīng)的費(fèi)用如表1所示。通過解決包含SCFC約束的最優(yōu)節(jié)點(diǎn)配置問題對(duì)應(yīng)混合整數(shù)模型[24]，最優(yōu)值為105，對(duì)應(yīng)的最優(yōu)解為（位置-節(jié)點(diǎn)）：{1-4，2-3，3-6，5-1，6-2，11-5}。

圖3 節(jié)點(diǎn)配置問題例子

下一步，我們嘗試了解決若干不同規(guī)模的網(wǎng)絡(luò)和節(jié)點(diǎn)數(shù)量的問題。以無向圖的模型為例，仿真結(jié)果如下圖所示，橫軸表示構(gòu)造的模型中整數(shù)變量的個(gè)數(shù)，縱軸表示的是通過分支界定算法尋找到最優(yōu)解的迭代次數(shù)。所有的規(guī)模都在有限次迭代中找到的最優(yōu)解，但顯而易見，隨著整數(shù)變量個(gè)數(shù)的增加，所需的迭代次數(shù)也飛速增加。

表1 放置節(jié)點(diǎn)的費(fèi)用

圖4 仿真數(shù)據(jù)

5 結(jié)論

文中建立了一個(gè)保持網(wǎng)絡(luò)連通性的最優(yōu)節(jié)點(diǎn)配置問題的優(yōu)化模型。在此基礎(chǔ)上，分別考慮了無向圖和有向圖的兩種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，提出了基于單一商品流約束構(gòu)造混合整數(shù)規(guī)劃的方法。最后使用用傳統(tǒng)的分支界定算法求解此問題的最優(yōu)解。通過解決這樣數(shù)學(xué)問題，我們可以解決很多真實(shí)世界中的具體工程問題，例如物流上的站點(diǎn)分配，無線傳感網(wǎng)絡(luò)中和連通性相關(guān)的傳感器配置等問題。