許 珂 ，陸 疌

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

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

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

1 最優(yōu)節(jié)點配置問題的實例

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

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

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

2 問題模型

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

2.1 目標函數(shù)

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

2.2 函數(shù)約束

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

2.2.1 資源配置約束

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

1）每個節(jié)點只能分配到一個位置；

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

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

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

2.3 數(shù)學模型

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

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

3 子圖的連通性約束

現(xiàn)如今，有很多學者提出了建立不同的優(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]。文中運用單一商品流約束來構(gòu)造最優(yōu)節(jié)點配置問題中的連通性約束。

3.1 無向圖的連通性約束

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

保持連通性的約束如下：

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

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

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

3.2 有向圖的連通性約束

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

保持連通性的約束如下：

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

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

4 仿真實驗

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

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

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

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

表1 放置節(jié)點的費用

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

5 結(jié)論

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