大學新城電信通訊網絡可靠性模型設計

〔摘 要〕本文利用Xpress-Mosel的建模和求解環境，通過約束條件的逐步逼近，用最大流問題來研究給定電信網絡的可靠性，從而實現大學新城內各高校之間數據通信的最優化方案。

〔關鍵詞〕大學新城；電信網絡；數據通信；最優化模型

〔中圖分類號〕TP311 〔文獻標識碼〕A 〔文章編號〕1008-0821(2009)02-0205-02

Reliability Model Design of Telecommunication Network in University TownWang Yufu

(Library，Shanghai University，Shanghai 201800，China)

〔Abstract〕By using the model and solution of Xpress-Mosel，through the constraints of successive approximation，with the largest flow to study the issue given the reliability of the telecommunications network.An optimization model was achieved which described the community network in university town.

〔Key words〕university town；telecom network；data communication；optimization model

近年來城市大學新城的建設為高等學校的發展提供了很大的、共享的辦學資源和空間，其中電信通信網絡的優化設計問題既要能夠滿足結點之間的期望通信流量，也要使建造費用最小，同時還應滿足可靠性要求。為此，我們將研究給定網絡中2個結點之間數據交換的可靠性，此可靠性可以用2個結點之間相互分離的路徑(即其中間結點均不相同的路徑)的數目K來度量。如果K＞1，則即使K-1個結點都停止工作之后這2個結點之間仍然能夠進行通信：我們給定的電信網絡如圖1所示，連接大學城內各高校的電信結點有11個，在結點之間存在雙向連接，以進行數據傳輸。出于可靠性的考慮，圖1所示的網絡中要求有任意3個結點被破壞時都不會中斷結點10和11之間的通信。

1 模型的數學表達

首先將該模型轉化為一個最大流[1]問題來討論：設G=(N，A)為一幅有向圖，其中N為結點的集合，A為弧的集合，(n，m)為結點n連接到結點m的弧，Cnm為弧(n，m)具有整數值的最小通達量。

設想如果在某個結點S+處有液體流入網絡，并且從圖1 大學新城網絡結點圖

結點S-處流出網絡，則液體將在網絡中四處流動。我們可以用fnm來表示每條弧(n，m)上的流，對于每個fnm都滿足它對應弧上的通過量限制，且在通過中間結點(也就是除了S+和S-之外的其它結點)時都不會有損耗，則認為此流合法。最大流問題即要尋找出能夠使在S+處注入的液體量最大的流(由于沒有損耗，因此也可以表示為使S-處流出的液體量最大)。如果將此問題表示為線性規劃模型，則單純形方法求得的最優解即為整數解[2]。

為了用最大流問題來研究給定電信網絡的可靠性，我們設定每條連接的最大通過量均為1：則在流為最優時，每條弧上的實際流量為0或1。我們再為每個結點規定其通過量限制為1，這樣，2個沿著2條不同的弧離開S=10的2個流單元將沿著不同的路徑到達T=10，這2條路徑上的結點均不相同，這樣的路徑稱為結點分離(node-disjunctive)的路徑。

由于離開S+的每條弧上的流均為0或1，因此，在有向圖G中從S+到S-的最大分離路徑數即等于圖1中的最大流通量。如果我們能夠找到k條路徑，則在k-1個結點損壞時，此網絡仍然為導通：在最糟糕的情況下，這些結點將分布于k-1條相互獨立的路徑上，但是通信仍然可以通過最后一條仍然導通的路徑進行。最后，通過比較k-1與圖中允許發生損壞的結點數目就可以得出我們所研究的可靠性問題的答案。

模型中還有一個問題是：流問題通常定義為有向圖，但我們要研究的網絡采用雙向連接，而非有向連接。為區分結點n和m之間2個方向上的流，我們將此連接表示為2條弧(n，m)和(m，n)，因此可以得到有向圖G，從而對此問題進行較為簡單的表達如下：

2009年2月第29卷第2期現?代?情?報Journal of Modern InformationFeb.2009Vol.29 No.2

2009年2月第29卷第2期大學新城電信通訊網絡可靠性模型設計Feb.2009Vol.29 No.2(1)目標函數為最大化總通量，即離開S+結點的所有流的通量之和(也是到達S-結點的所有流通量之和)如(1)式：

Maximize∑m是n的后一結點fmn(1)

(2)從所有前一個結點到來的流總量應等于去往下一結點的流總量，即每個中間結點n上的流守恒定理(也稱為Kichhoff定理[1])可用約束條件(2)來滿足之：

n≠S+，S-∶∑m是n的后一結點fnm=∑m是n的前一結點fmn(2)

(3)考慮離開每個結點的流，約束條件(3)將使每個中間結點上的流量上限為1：

n≠S+，S-∶∑m是n的后一結點fnm1(3)

(4)為了避免從S+發出的流再次回到S-結點，需要加入約束條件：

∑m是S+的前一結點fm，S+=0(4)

(5)約束條件(5)將指定所有流變量 均為二值變量：

(n，m)∈A∶fnm∈{0，1}(5)

2 模型實現

上述數學模型可以通過下面的Mosel程序來實現。我們用鄰接矩陣[2]的形式對一個具有N個結點的圖進行編碼：設鄰接矩陣A是一個大小為N×N的二值矩陣，如果弧(n，m)存在，則最大通過量Anm=1。在數據文件中此數組將保存為稀疏形式，即在其中只以(n m)A(n，m)的形式給出了A的非零元素。如果在程序中需要使用A中未定義的元素，則它們均取默認值0，但我們可以使用Mosel函數exists來測試找出A中有定義的元素，從而有效地枚舉出此矩陣的各個元素，當其中有定義的元素非常少時這種方法效率很高。

為得到更為簡潔的模型，從而使線性規劃問題規模縮小，以便加快求解速度，我們只定義了那些對應于實際存在的弧的變量fnm，而且數據文件中以無向的形式對此圖進行表示：結點n和m之間的雙向連接在圖中只出現1次(約定n＜m)。因此要構造出圖的有向版本：對于每條有定義的弧(n，m)，均定義它的反(m，n)，此版本將用于最大流模型表達。模型的其它部分可以直接從數學模型轉換而來，無論選擇網絡中的哪兩個結點作為S+和S-。都可以使用此模型。

Model Telecom !將其命名為telecom..mos

uses″mmxprs″ !將使用Xpress-Optimizerdeclarations

N：range !結點集合

S+=10；S-=11 !源和宿結點

A：array(N，N)of integer !如果弧有定義，則取值為1，否則為0

f：array(N，N)of mpvar !如果弧上有流，則取值為1，否則為0

end-declarationsinitializations from’telecom.dat’

A

end-initializationsforall(n，m in N|exists(A(n，m))and n＜m)A(m，n)：=A(n，m)

forall(n，m in N|exists(A(n，m)))create(flow(n，m))

Paths：=sum(n in N) flow(S+，n) !目標函數：獨立路徑的數目

forall(n in N|n＜＞and n＜＞)do

sum(m in N)flow(m，n)=sum(m in N)flow(n，m)

sum(m in N)flow(n，m)＜=1 !流守恒和通量限制

end-dosum(n in N)flow(n，S+)=0

forall(n，m in N|exists(A(n，m)))flow(n，m)isbinary !不允許返回S+結點!求解此問題

maximize(Paths)!打印求解結果

writeln(″Total number of paths：″，getobjval)

forall(n in N|n＜＞S+ and n＜＞S-)

if(getsol(flow(S+，n))＞0)then

write(S+，″-″，n)

nnext：=n

while(nnext＜＞S-)do

nnext：=round(getsol(sum(m in N) m*flow(nnext，m)))

write(″-″，nnext)

end-do

writeln

end-if

end-model

注意，在打印輸出求解結果時，使用了一個小算法來打印出S+和S-結點之間的所有路徑：對于每個有來自S+結點的流注入的結點，計算出其后輩結點鏈，直到到達S-結點。為求得結點n的后輩結點，我們需要利用每個中間結點在1個路徑中只能出現1次因而只能有1個后輩結點這個事實。我們計算所有離開結點n的流乘以對應的后一結點的索引值，然后進行求和，這樣就得到了n的后輩結點的索引。Getsol的返回值為實數，因此需要使用函數round將其轉化為整數值。

3 結 語

此求解算法計算出最大總通量為4，這意味著在結點10和11之間有4條相互分離的路徑，因此，當有3個中間結點損壞時，這2個結點之間仍然能夠會繼續進行通信。即要求能夠得到滿足。如圖2給出了結點10和11之間的4條分離路徑(圖中實線)。

圖2 結點10和11之間4條分離路徑圖

參考文獻

[1]R.K.Ahuja，T.L.Magnanti，and J.B.Orlin.Network Flows.Theory，Algorithms and pplications.Prentice Hall，Englewood Cliffs，NJ，1993.

[2]S.Baase.Computer Algorithms.Addison-Wesley，1988.

[3]E.D.Andersen and K.D.Andersen.Presolving in Linear Programming.Mathematical Programming，1995，71(2)：221-245.

[4]C.Prins，Algorthmes de graphes avec programmes en Pascal.Eyrolles，1994.

[5]C.H.Papadimitriou and K.Steiglitz.Combinatorial Optimization.Dover，1998.