〔摘 要〕本文利用Xpress-Mosel的建模和求解環(huán)境，通過約束條件的逐步逼近，用最大流問題來研究給定電信網(wǎng)絡(luò)的可靠性，從而實(shí)現(xiàn)大學(xué)新城內(nèi)各高校之間數(shù)據(jù)通信的最優(yōu)化方案。

〔關(guān)鍵詞〕大學(xué)新城；電信網(wǎng)絡(luò)；數(shù)據(jù)通信；最優(yōu)化模型

〔中圖分類號(hào)〕TP311 〔文獻(xiàn)標(biāo)識(shí)碼〕A 〔文章編號(hào)〕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

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

1 模型的數(shù)學(xué)表達(dá)

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

設(shè)想如果在某個(gè)結(jié)點(diǎn)S+處有液體流入網(wǎng)絡(luò)，并且從圖1 大學(xué)新城網(wǎng)絡(luò)結(jié)點(diǎn)圖

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

為了用最大流問題來研究給定電信網(wǎng)絡(luò)的可靠性，我們?cè)O(shè)定每條連接的最大通過量均為1：則在流為最優(yōu)時(shí)，每條弧上的實(shí)際流量為0或1。我們?cè)贋槊總€(gè)結(jié)點(diǎn)規(guī)定其通過量限制為1，這樣，2個(gè)沿著2條不同的弧離開S=10的2個(gè)流單元將沿著不同的路徑到達(dá)T=10，這2條路徑上的結(jié)點(diǎn)均不相同，這樣的路徑稱為結(jié)點(diǎn)分離(node-disjunctive)的路徑。

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

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

2009年2月第29卷第2期現(xiàn)?代?情?報(bào)Journal of Modern InformationFeb.2009Vol.29 No.2

2009年2月第29卷第2期大學(xué)新城電信通訊網(wǎng)絡(luò)可靠性模型設(shè)計(jì)Feb.2009Vol.29 No.2(1)目標(biāo)函數(shù)為最大化總通量，即離開S+結(jié)點(diǎn)的所有流的通量之和(也是到達(dá)S-結(jié)點(diǎn)的所有流通量之和)如(1)式：

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

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

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

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

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

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

∑m是S+的前一結(jié)點(diǎn)fm，S+=0(4)

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

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

2 模型實(shí)現(xiàn)

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

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

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

uses″mmxprs″ !將使用Xpress-Optimizerdeclarations

N：range !結(jié)點(diǎn)集合

S+=10；S-=11 !源和宿結(jié)點(diǎn)

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) !目標(biāo)函數(shù)：獨(dú)立路徑的數(shù)目

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+結(jié)點(diǎn)!求解此問題

maximize(Paths)!打印求解結(jié)果

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

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

3 結(jié) 語

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

圖2 結(jié)點(diǎn)10和11之間4條分離路徑圖

參考文獻(xiàn)

[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.