列車通信網絡設計問題中的雙層規劃模型

田寅,賈利民,董宏輝,李海艦

(北京交通大學軌道交通控制與安全國家重點實驗室, 100044, 北京)

列車通信網絡設計問題中的雙層規劃模型

田寅,賈利民,董宏輝,李海艦

(北京交通大學軌道交通控制與安全國家重點實驗室, 100044, 北京)

列車通信網絡的物理拓撲結構和邏輯拓撲結構優化問題關系到列車控制系統及安全監測系統的性能和經濟效益。對列車通信網絡的設計問題進行建模,通過雙層規劃的思想,將列車通信網絡的可靠性、建造費用與通信效率納入統一的決策過程,從而建立科學的列車通信網絡最優性能模型。上層規劃以最低建造成本為目標,約束條件為網絡可靠性;下層規劃以最大通信效率為目標,約束條件為建造費用和網絡物理拓撲。最后利用一種基于遺傳算法和Floyd算法的混合求解過程對列車通信網絡綜合規劃模型進行求解,得到滿足網絡穩定性要求下的最小費用設計方案及該方案下的最優效率通信方式。通過對實例結果的分析表明,文中提出的模型是切實有效的。

列車通信網絡;雙層規劃;遺傳算法;可靠性

隨著網絡通信技術的發展,越來越多的新型通信網絡結構被提出,用于替代列車上原有的列車控制網絡(TCN)。列車通信網絡的拓撲結構將直接影響網絡的性能,如果其結構設計不當,將會導致網絡的可靠性下降,時延增加,從而進一步影響整體網絡的性能。

目前,有大量優化網絡拓撲結構設計的方法,其中大多數僅覆蓋網絡設計問題中的一部分,例如網絡中的某些組成設備[1],或者某些特性[2],而沒有系統化地對網絡整體需求進行探討。一些方法探討了可靠性約束下的網絡拓撲設計[3],以求建立一條穩定性最大的網絡。一些方法探討了如何根據費用約束及應用環境需求確定網絡的物理拓撲結構,以獲得最大可靠性[4],但是這些方法未考慮網絡在時延方面的需求。一些文獻探討了網絡中減小時延的方法[5-6],這些方法大多是在物理拓撲已知的網絡中,通過對通訊協議或者某些設備的替換,來實現網絡實時性的優化。此外,還有一些文獻嘗試探討了如何對網絡的物理拓撲和邏輯拓撲同時進行優化[7],但是沒有提出一種較為通用的系統優化模型。一般而言,現有文獻將這種同時考慮物理拓撲和邏輯拓撲的網絡設計過程看作是一種多目標優化方法[8],但是這種思想導致算法求解變得異常復雜,并且不能確保獲得最優解。

本文借助雙層規劃的思想[9]來實現在費用約束下,同時滿足通信網絡可靠性和實時性最優的設計過程。將列車通信網絡的物理拓撲規劃看作一個離散網絡規劃問題,將邏輯拓撲規劃看作一個最短時延規劃問題,本文基于這兩個問題建立雙層規劃模型,并提出一種求解方法。

1 離散列車通信網絡雙層規劃模型

1.1 用于求解離散網絡規劃問題的雙層規劃模型

列車控制系統的核心是列車通信網絡,最重要的兩個指標是可靠性和時延。由于受物理結構的限制,傳統列車通信網絡的可靠性和實時性存在一些缺陷。首先,傳統列車通信網絡內所有的節點串聯在一起,整個網絡呈線性鏈接,因此只要其中一條鏈路損壞,整個網絡都將無法工作。另外,網絡內部所傳輸的數據位于線狀鏈路兩端時會變得異常擁擠,從而使時延增大。

由于以太網技術已經被引入到列車通信網絡設計中,本文嘗試打破傳統的節點間連接方式,通過有效地規劃節點間的鏈路,實現網絡可靠性和時延的最優化。受時延限制的列車通信網絡拓撲規劃問題可以表示為如下的雙層規劃模型

(1)

s.t.G(x,u)≤0

(2)

(3)

s.t.g(x,u)≤0

(4)

上述雙層規劃模型包含兩個子模型,(P)為上層問題,也就是網絡物理拓撲規劃問題;(L)是下層問題,也就是網絡邏輯拓撲規劃問題;F和u是物理拓撲規劃問題的目標函數和決策向量;G是(P)問題的決策向量的約束條件;f和x是邏輯拓撲規劃問題的目標函數和決策向量;g是(L)問題的決策向量的約束條件。

1.2 物理拓撲優化問題

傳統意義上,在研究通信網絡的可靠性問題時,假定節點和鏈路的可靠性是隨機而且相互獨立的,但是這些可靠性都已知并且固定。由于列車通信網絡上所有信息都是雙向傳輸,因此可用無向圖來描述列車通信網絡。假設G=(N,L,A)是一個沒有平行鏈路的網絡,并且網絡中沒有孤立點存在,則費用約束的網絡可靠性優化問題(即上層物理拓撲優化)可以用如下模型來表示

(5)

(6)

P(lj)=F1(c(lj))

(7)

P(ni)=F2(c(ni))

(8)

式中:R(x)是整個網絡的可靠性;P(lj)是鏈路lj的可靠性;P(ni)是節點ni的可靠性;Ω是網絡所有可用狀態的集合;C(x)是整個系統的最大可使用費用;c(lj)是每單位距離鏈路j的費用;dj是鏈路j的長度;c(ni)是節點i的費用;L是鏈路個數;N是節點個數;F1是鏈路可靠性與鏈路單價之間的函數關系;F2是節點可靠性與節點成本之間的函數關系。在任意時間段,G中都只有部分鏈路能夠工作,此時G的狀態是有向圖(N,L,A)的子圖(N,L′),其中L′是正常工作鏈路的集合。如果lj∈L′,那么uj=1,否則uj=0。

在上層的物理拓撲優化問題中,網絡設計者的目標是通過改變連接方式來獲得最大的網絡可靠性。約束條件(6)保證了網絡的建設總費用不會超過規定的最大費用,約束條件(7)和(8)描述了網絡設備的可靠性與費用之間的函數關系。

1.3 邏輯拓撲優化

邏輯拓撲優化的目標是使傳輸時延最短。同傳統列車通信網絡中傳輸的控制指令大小相比,以太網能承載的數據量非常巨大,因此假設網絡帶寬足夠大,不會影響數據的實時性。這樣,數據流的邏輯拓撲優化問題實際上是一個在網絡物理拓撲限定下的最小時延問題。列車通信網絡的邏輯拓撲優化問題(即下層邏輯拓撲優化)可以表述為

(9)

s.t.Φ∈Ω

(10)

c(lj)=f1(t(lj))

(11)

c(nj)=f2(t(nj))

(12)

式中:T(x)是系統的總時延;t(lj)是鏈路lj上的延時;t(ni)是節點ni的延時;數據從節點向另一任意節點傳輸時,通過的傳輸路徑是G的一個子集,記做(N′,L″);f1是鏈路時延與鏈路單價之間的函數關系;f2是節點時延與節點成本之間的函數關系。

在這個模型中,網絡的設計者希望信息按照設定的方式傳輸,因此網絡的下層規劃實際上是在物理拓撲一定的情況下,對邏輯拓撲進行優化的過程。約束條件(10)保證了邏輯鏈路的選擇是在已知的物理拓撲下完成的,約束條件(11)和(12)描述了網絡設備的時延與費用之間的函數關系。

2 列車通信網絡雙層規劃模型求解

一般情況下,雙層規劃的優化問題是很難求解的[10]。對通信網絡可靠性、時延及成本的優化問題是一個NP-C問題,因此遺傳算法是一種合適的求解方法,近年來已經被大量地用于非線性問題的優化中。大量的文獻研究表明,遺傳算法可以有效地解決網絡性能優化的問題[11]。

在通常情況下,某種設備的可靠性與費用成正比,時延與費用成反比。因此,模型下層L1中的費用約束條件可以通過特定的費用轉移至上層約束中,以便于模型的求解。

根據列車通信網絡雙層規劃模型的特點,本文采用模塊化的設計思想,提出一種基于遺傳算法與Floyd算法的求解過程,算法步驟如下。

步驟1設定初始參數,包括節點數目、節點間距離、最大費用、節點單價、節點可靠性、鏈路單價和鏈路可靠性。

步驟2根據初始參數,生成初始基因并利用遺傳算法對節點間的物理連接方式進行規劃,并在最大費用約束條件下,生成最優解。

步驟3判斷物理拓撲結構是否符合實際要求,如果符合,進入步驟4。否則,將該結果記錄進不合適解數據庫后進入步驟2,重新尋找除去不合適解外的最優解。

步驟4將最優解的基因轉化成表征物理拓撲結構的鄰接矩陣,并傳遞給邏輯拓撲規劃模塊。進行邏輯拓撲規劃,尋找網絡中任意兩個節點間的時延最小的通信方式,生成節點間邏輯拓撲規劃表。

步驟5判斷邏輯拓撲是否符合要求,如果符合要求,結束全部算法。否則,將該結果記錄進不合適解數據庫并判斷原因,如果是邏輯拓撲規劃導致,則重新進行步驟4,否則進行步驟2。

2.1 求解邏輯拓撲優化問題的遺傳算法

2.1.1 編碼方式 在雙層規劃過程中,非常關鍵的一個步驟是如何有效地將信息在兩層優化中傳遞,其中有效的基因編碼方式又是十分重要的一部分。基因編碼的第一步是確定基因的長度。對于一個有Nd個節點的列車通信網絡,其包含的鏈路數Nl與節點數Nd之間的關系為

(13)

因此,為了表征整體網絡的可靠性,本文提到的算法中所用的基因應該有0.5(Nd+1)Nd+Nd位,開始的|0.5(Nd+1)Nd|位表征鏈路的可靠性,接下來的|Nd|位表征節點的可靠性。

對于不同的節點及鏈路,用不同的整數代表其可靠性,例如數字1代表可靠性最好的設備,數字2代表可靠性次之的設備等等。如果有N種不同可靠性的設備,那基因中每一個位的取值范圍是[0,N],其中0代表鏈路不存在。

與傳統的用遺傳算法求解網絡可靠性的研究不同,本文所提方法除了得出最優解外,還需要將網絡結構傳遞至下層的邏輯拓撲規劃,因此基因的編碼必須要能體現出被傳遞網絡的結構特征。通常利用網絡的伴隨矩陣來表征網絡結構,因此基因的結構也從伴隨矩陣中演變而來。圖1顯示了網絡的伴隨矩陣a與基因g的關系。

圖1 基因與伴隨矩陣的關系

2.1.2 適應度函數 優化的目標是尋找費用約束條件下最可靠的物理拓撲結構,因此適應度函數必須包含費用和可靠性兩個因素。由于處于最優邊界上的解往往是一個可行解和一個不可行解的后代,因此在設置適應度函數時,不能單純地將不可行解剔除。合理的解決方案是設置一種有效的懲罰函數,用以降低不可行解在種群中的比重。根據實際實驗發現,采用如下適應度函數具有較好的運算效率

(14)

式中:C是系統允許的最大費用;count(r(g))≠0表示g的可達矩陣r(g)中0的個數,該限制條件保證了列車通信網絡中不會存在孤立節點;R(x)是系統可靠性;c(x)是系統實際費用;λ是懲罰因子,根據實際情況設定,λ

2.1.3 基因操作 種群數量、選擇方法、交叉及變異操作、停止條件等參數決定了遺傳算法的效率。通過大量的實驗,選擇出最適合本文中算法的遺傳算法參數。種群數量為400,同時限制種群中每個基因的取值范圍為1到N的整數。采用隨機均勻的基因篩選方法,使用交叉概率為0.8的單點交叉方法,使用突變率為0.03的均勻突變,終止條件為遺傳500代。

2.2 求解邏輯拓撲優化問題的算法

首先假設列車通信網絡中各節點間的最小通信時延僅與節點間的最短路徑有關,并且最短路徑與鏈路長度無關,也就是網絡中一條信息傳遞的時間只與其經過的節點數有關。下面說明該假設的合理性。

眾所周知,通信網絡的時延為

T=Ttd+Tpd+Tqd

(15)

式中:Ttd是發送時延;Tpd是傳輸時延;Tqd是排隊時延。但是,對于列車通信網絡來說,最大鏈路長度不會超過200m,因此網絡中的傳輸時延可忽略不計。發送時延與排隊時延都是由轉發產生的,所以在對網絡通信時延進行最優化時,只考慮信息傳遞過程中經過了多少次轉發,也即經過了多少個節點。

由于優化目標是尋找列車通信網絡系統內每一個節點與其他節點通信時的最短路徑,這屬于一種全局最短路問題,因此可采用Floyd算法。該算法已經大量地應用于網絡最短路問題的求解過程中。對本文所提方法而言,運用Floyd算法關鍵是將上層物理規劃中獲得的最優基因轉換成求解Floyd算法所需要的伴隨矩陣。本文方法是利用3.1節中基因g與伴隨矩陣a的關系,重新將基因轉化成伴隨矩陣。

3 數值算例

通過兩個算例驗證了本文所提算法的準確性和有效性,并給出實際問題的解決案例。

3.1 算例1

假設有3種不同可靠性及費用的鏈路及節點,如表1、表2所示。

表1 鏈路可靠性與費用關系對照表

表2 節點可靠性與費用關系對照表

另假設網絡中有4個節點成線性排列,相鄰節點間隔40m。經計算可知,要實現這樣一個系統,其最小費用是6960,結構如圖2a所示,此時的網絡可靠性最小,為0.22。最大費用是18 000,結構如圖2b所示,此時的網絡可靠性最大,為0.81。

(a)4個節點時費用最低的解

(b)4個節點時費用最高的解

下面用本文設計的算法,分別將費用約束設定為6960及18 000,懲罰因子λ=0.1,觀察運行得到的結果是否符合實際情況。算法運行完成后的結果如圖3、圖4所示。由圖3可見,費用約束為6960時,在100代左右出現最優解,最優解約為0.2202。由圖4可見,費用約束為18 000時,約在第10代出現最優解,最優解約為0.814 7。可知,利用本文提出的列車通信網絡雙層規劃算法,上層物理拓撲規劃及下層邏輯拓撲規劃都能夠產生符合要求的解。

(a)費用為6960時的迭代結果

(b)費用為6960時的基因

(a)費用為18 000時的迭代結果

(b)費用為18 000時的基因

3.2 算例2

假設現在有一個6節車廂編組的列車,每節車廂中有一個節點需要與其他車廂中的節點連接。該6節編組列車原型為廣州地鐵2號線上運行的車輛,每節車長26m。考慮布線方式,假設要連接相鄰兩個節點,需要50m的電纜。鏈路及節點的費用和可靠性仍然參考表1和表2。分別求解最大建造費用為17 000及25 000時,最穩定網絡結構及最短時延通信方式。考慮信號衰減問題,系統中的最大鏈路長度必須小于或等于150m。

利用本文所述方法,得到列車中節點連接方式的最優解物理連接方式如圖5所示,圖中從左至右依次為A-F節點。C(x)=17 000時,最佳邏輯鏈路為A-B;A-C;A-C-D;A-C-E;A-C-E-F;B-C;B-D;B-D-E;B-D-F;C-D;C-E;C-E-F;D-E;D-F;E-F。C(x)=25 000時,最佳邏輯鏈路為A-B;A-C;A-D;A-D-E;A-D-F;B-C;B-D;B-D-E;B-D-F;C-D;C-D-E;C-F;D-E;D-F;E-F。

(a)C(x)=17 000

(b)C(x)=25 000

對比兩個不同限制的優化條件可以發現:隨著費用的增加,列車通信網絡系統的可靠性增加;由于鏈路數目的增加,網絡系統的時延也在降低。可以發現,在費用有限時,應該盡可能地增加鏈路數目,形成冗余連接,而不是選用高可靠性的設備。

4 結 論

本文提出了列車通信網絡優化問題的普適描述,以及一種能夠在費用約束下得到列車通信網絡可靠性及時延同時最優的設計方法。通過雙層規劃的思想,本文將列車通信網絡設計問題分成位于上層的物理拓撲規劃問題及位于下層的邏輯拓撲規劃問題,完整地實現了列車通信網絡的優化過程。

本文提出列車通信網絡雙層規劃模型的求解方法。通過改進的遺傳算法,本文設計了合理的基因表示方法,結合遺傳算法與Floyd算法,有效地將物理拓撲優化結果傳遞至下層優化過程中。

本文所提方法能夠有效地尋找到費用、可靠性及時延三者的平衡點,并且由于采用了模塊化的設計,該方法便于更換約束條件,以適用于不同目的和特定約束的列車通信網絡優化問題。

通過實例分析可知,本文所提方法是合理的,并且能夠解決相應的實際問題,但該方法沒有考慮鏈路在通過車廂時的可靠性變化問題,這個問題可作為邏輯拓撲設計問題中的一個附加條件。雖然這一問題并不會改變本文算法中費用、可靠性及實時性的關系,但是會影響實際施工過程中對設備的選擇,這將是未來的一個研究方向。

[1] MORENO J C, LALOYA E, NAVARRO J.A link-layer slave device design of the MVB-TCN bus [J].IEEE Transactions on Vehicular Technology, 2007, 56(6): 3457-3468.

[2] 邢震, 賈步超, 穆建成, 等.基于交換式以太網的TCN設計與實時性能分析 [J].鐵路計算機應用, 2013, 22(6): 51-56.

XING Zhen, JIA Buchao, MU Jiancheng, et al.Design and real-time performance analysis on switched ethernet based train communication network [J].Railway Computer Application, 2013, 22(6): 51-56.

[3] SZLACHCIC E.Fault tolerant topological design for computer networks [C]∥Proceedings of the 2006IEEE International Conference on Dependability of Computer Systems.Piscataway, NJ, USA: IEEE, 2006: 150-159.

[4] SHAO Fangming, SHEN Xuemin, HO Pinhan.Reliability optimization of distributed access networks with constrained total cost [J].IEEE Transactions on Reliability, 2005, 54(3): 421-430.

[5] UNZUETA H, JIMENEZ J, MARTIN J L, et al.An emulator to develop the Wire Train Bus protocol stack [C]∥Proceedings of the 32nd Annual Conference on IEEE Industrial Electronics Society.Piscataway, NJ, USA: IEEE, 2006: 3721-3726.

[6] 趙洪華, 陳鳴.利用往返時延抖動的網絡拓撲推斷算法 [J].西安交通大學學報, 2009, 10(2): 28-32.

ZHAO Honghua, CHEN Ming.A topology inference algorithm using round delay variation [J].Journal of Xi’an Jiaotong University, 2009, 10(2): 28-32.

[7] FENCL T, BURGET P, BILEK J.Network topology design [J].Control Engineering Practice, 2011, 19(11): 1287-1296.

[8] WANG Chenshu, CHANG Chingter.Integrated genetic algorithm and goal programming for network topology design problem with multiple objectives and multiple criteria [J].IEEE/ACM Transactions on Networking, 2008, 16(3): 680-690.

[9] CHEN Yongrong.Model and algorithm for discrete network equilibrium design problem [C]∥Proceedings of the 2nd International Conference on Uncertainty Reasoning and Knowledge Engineering.Piscataway, NJ, USA: IEEE, 2012: 166-169.

[10]VICENT L N, CALAMAI P H.Bilevel and multilevel programming: a bibliography review [J].Journal of Global Optimization, 1994, 5(3): 291-306.

[11]KUMAR A, PATHAK R M, GUPTA Y P.Genetic-algorithm-based reliability optimization for computer network expansion [J].IEEE Transactions on Reliability, 1995, 44(1): 63-72.

[本刊相關文獻鏈接]

鄭豪,張興軍,王恩東,等.一種采用驅動隔離的宿主機可靠性方法.2013,47(10):7-12.[doi:10.7652/xjtuxb201310002]

王兆杰,高峰,翟橋柱,等.高耗能企業關口平衡問題的雙目標規劃模型.2013,47(8):26-32.[doi:10.7652/xjtuxb201308005]

汪志偉,曹建福,鄭輯光.一種面向分簇無線傳感器網絡的多信道跨層協議.2013,47(6):61-67.[doi:10.7652/xjtuxb 201306011]

李碩,王學望,康銳.面向完整性要求的航空電子全雙工交換式以太網可靠性評價參數研究.2013,47(3):126-131.[doi:10.7652/xjtuxb201303023]

伍文,孟相如,馬志強,等.模塊化動態博弈的網絡可生存性態勢跟蹤方法.2012,46(12):18-23.[doi:10.7652/xjtuxb 201212004]

宋婧,叢犁,葛建華,等.雙層網絡中一種協作博弈的動態資源分配方法.2012,46(10):89-94.[doi:10.7652/xjtuxb2012 10016]

覃慶努,魏學業,韓磊,等.電子系統的Markov模型和云可靠性評價方法.2012,46(8):87-93.[doi:10.7652/xjtuxb 201208016]

楊柳靜,秦濤,王晨旭.應用交互式網絡流模型的高速網絡異常行為檢測與控制.2012,46(6):58-65.[doi:10.7652/xjtuxb201206011]

侯重遠,江漢紅,芮萬智,等.工業網絡流量異常檢測的概率主成分分析法.2012,46(2):70-75.[doi:10.7652/xjtuxb 201202012]

劉逵,劉三陽,馮海林.雙信道無線傳感器網絡移動代理路由算法.2012,46(2):113-118.[doi:10.7652/xjtuxb201202019]

張文健,田茂,何浩,等.分層網絡下行中斷概率的閉式表達.2011,45(12):59-63.[doi:10.7652/xjtuxb201112011]

鄢民強,楊波,王展.不完全覆蓋的模糊多狀態系統可靠性計算方法.2011,45(10):109-114.[doi:10.7652/xjtuxb201110020]

張瑩,殷勤業,穆鵬程.利用均勻線陣實現高移動性通信系統中的多普勒補償.2011,45(8):73-77.[doi:10.7652/xjtuxb 201108013]

池信澤,周顥,趙保華.面向前向糾錯的無線Mesh網多播差錯控制協議.2011,45(8):30-36.[doi:10.7652/xjtuxb2011 08006]

李黎,管曉宏,趙千川,等.網絡生存適應性的多目標評估.2010,44(10):1-7.[doi:10.7652/xjtuxb201010001]

(編輯 武紅江)

BilevelProgrammingModelofTrainCommunicationNetworkDesign

TIAN Yin,JIA Limin,DONG Honghui,LI Haijian

(State Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong Unversity, Beijing 100044, China)

Train communication network physical topology and logical topology optimization usually drive the performances and economic benefits of the train control system and safety monitoring system.A model for designing train communication network is established.Following the essence of bi-level programming, the reliability, construction cost and communication efficiency are taken into account in decision-making process to suggest a scientific optimal performance model for designing train communication network.At the upper level, lowering construction cost is taken as the objective and constrained by network reliability.At the lower level, the maximum communication efficiency is taken as the objective and constrained by construction cost and physical topology.A hybrid method based on both genetic algorithm and Floyd algorithm is used to obtain an approach with higher reliability and lowest cost , and an example verifies the effectiveness of this model.

train communication network; bi-level programming; genetic algorithm; reliability

2013-09-20。

田寅(1986—),男,博士生;賈利民(通信作者),男,教授。

國家高技術研究發展計劃資助項目(2011AA110505);北京市科技新星計劃資助項目(Z1211106002512027)。

時間:2014-01-16

10.7652/xjtuxb201404023

U283.2

:A

:0253-987X(2014)04-0133-06

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20140116.1601.002.html