一種城軌列車網絡拓撲優化方法
2023-08-02 07:15:16
一種城軌列車網絡拓撲優化方法
【專利摘要】本發明公開了屬於軌道交通通信網絡【技術領域】的一種城軌列車網絡拓撲優化方法。本發明藉助雙層規劃的思想來實現在經濟性約束下，同時滿足通信網絡可靠性和實時性的優化設計過程；所述雙層規劃是將列車網絡的物理拓撲的規劃看作一個離散網絡規劃，而邏輯拓撲規劃看作一個最短時延規劃，並採用基於基因遺傳算法求解雙層規劃模型；通過本發明的優化方法能夠有效的尋找到費用，可靠性及時間三者的平衡點。本發明針對給定實例給出了基於基因遺傳算法的求解結果，說明本發明能夠應用到實際工程問題中，本發明應用到軌道交通列車網絡建設中能夠使列車網絡更加經濟、高效地運行有效節約建設成本，減少不必要的浪費和冗餘。
【專利說明】一種城軌列車網絡拓撲優化方法
【技術領域】
[0001]本發明屬於軌道交通通信網絡【技術領域】，特別涉及一種城軌列車網絡拓撲優化方法。
【背景技術】
[0002]隨著網絡通信技術的發展，越來越多的新型通信網絡結構被提出，用於替代列車上原有的TCN網絡。同時，也有研究希望在列車上建立一條專門用於安全監測的網絡。列車通信網絡的拓撲結構將直接影響網絡的性能。結構設計不當，將會導致網絡的可靠性下降，時延增加，從而進一步的影響整體網絡的性能。
[0003]目前有大量針對網絡拓撲結構設計優化的算法。但其中大多數都只針對網絡設計問題中的一部分進行研究，例如網絡中的某些組成設備，或者某些特性，而沒有系統化的對網絡整體需求進行探討。有一些算法探討了可靠性約束下的網絡拓撲設計，建立一條穩定性最大的網絡。有一些算法探討了如何根據經濟約束及應用環境需求確定網絡的物理拓撲結構，以獲得最大可靠性。但這些算法都沒有考慮網絡在時延方面的需求。一些算法探討了網絡中減小時延的方法,這些方法大多是在物理拓撲已知的網絡中，通過對通訊協議或者某些設備的替換，來實現網絡實時性的優化。有論文採用從頂至底的方法去設計列車通信網絡，但是其關注的重點是網絡的硬體層面，因此討論的是設備的晶片級設計。有一些論文嘗試探討了如何對網絡的物理拓撲和邏輯拓撲同時進行優化，但是沒有提出一種較為通用的系統優化模型。一般而言，現有文獻將同時考慮物理拓撲和邏輯拓撲的網絡設計過程看作是一種多目標優化方法，但是這種思想導致算法求解變得異常複雜，並且不能確保獲得最優解。
【發明內容】
[0004]本發明的目的是提供一種城軌列車網絡拓撲優化方法，其特徵在於，藉助雙層規劃的思想來實現在經濟性約束下，同時滿足通信網絡可靠性和實時性的優化設計過程；所述雙層規劃是將列車網絡的物理拓撲的規劃看作一個離散網絡規劃，而邏輯拓撲規劃看作一個最短時延規劃，並採用基於基因遺傳算法求解雙層規劃模型；在離散列車通信網絡拓撲規劃中，物理拓撲是鏈路與節點的優化布設，通過改變已有通信節點間的鏈路，使網絡可靠性達到要求，同時建造成本最小；邏輯拓撲是一個信息流路徑的均衡分配，其目標函數為網絡時延最小，傳遞函數X=X(U)將物理拓撲規劃的信息傳遞給邏輯拓撲，邏輯拓撲規划過程根據該函數設計合理的數據傳輸路徑；所述城軌列車網絡拓撲優化方法，含有以下步驟:
[0005]( I)設定初始參數，包括節點數目，節點間距離，最大費用，節點單價，節點可靠性，鏈路單價和鏈路可靠性；
[0006]設定初始參數是在假設網絡帶寬遠大於網絡內的數據量的基礎上，所述邏輯拓撲規劃能獲取網絡的最小時延；該假設的依據是現有列車通信網絡TCN，其最大帶寬為1.5Mbps，而用乙太網作為列車通信網後，帶寬將增加至100Mbps，即使現有控制指令增加10倍，網絡帶寬也要比數據流量大一個數量級；
[0007](2)根據初始參數，生成初始基因並利用遺傳算法對節點間的物理連接方式進行規劃，並在最大費用約束條件下，生成最優解；
[0008]假設G=(N，L, A)是一個沒有平行鏈路的網絡，並且網絡中沒有孤立點存在，受費用約束的網絡物理拓撲結構可靠性表述成為:
【權利要求】
1.一種城軌列車網絡拓撲優化方法，其特徵在於，藉助雙層規劃的思想來實現在經濟性約束下，同時滿足通信網絡可靠性和實時性的優化設計過程；所述雙層規劃是將列車網絡的物理拓撲的規劃看作一個離散網絡規劃，而邏輯拓撲規劃看作一個最短時延規劃，並採用基於基因遺傳算法求解雙層規劃模型；在離散列車通信網絡拓撲規劃中，物理拓撲是鏈路與節點的優化布設，通過改變已有通信節點間的鏈路，使網絡可靠性達到要求，同時建造成本最小；邏輯拓撲是一個信息流路徑的均衡分配，其目標函數為網絡時延最小，傳遞函數X=X(U)將物理拓撲規劃的信息傳遞給邏輯拓撲，邏輯拓撲規划過程根據該函數設計合理的數據傳輸路徑；所述城軌列車網絡拓撲優化方法，含有以下步驟: (1)設定初始參數，包括節點數目，節點間距離，最大費用，節點單價，節點可靠性，鏈路單價和鏈路可靠性； 設定初始參數是在假設網絡帶寬遠大於網絡內的數據量的基礎上，所述邏輯拓撲規劃能獲取網絡的最小時延；該假設的依據是現有列車通信網絡TCN，其最大帶寬為1.5Mbps,而用乙太網作為列車通信網後，帶寬將增加至100Mbps，即使現有控制指令增加10倍，網絡帶寬也要比數據流量大一個數量級； (2)根據初始參數，生成初始基因並利用遺傳算法對節點間的物理連接方式進行規劃，並在最大費用約束條件下，生成最優解； (3)判斷物理拓撲結構是否符合實際要求，如果符合，進入第四步；否則，將該結果記錄進不合適解資料庫後進入第二步，重新尋找除去不合適解外的最優解；其物理拓撲受限於除經濟約束外的約束條件:列車通信網絡中不能存在孤立的節點，以及由於線纜條件制約而產生的最大鏈路約束； (4)將最優解的基因轉化成表徵物理拓撲結構的鄰接矩陣，並傳遞給邏輯拓撲規劃模塊；進行邏輯拓撲規劃，尋找網絡中任意兩個節點間的時延最小的通信方式，生成節點間邏輯拓撲規劃表； (5)判斷邏輯拓撲是否符合要求，如果符合要求，結束全部算法；否則，該結果記錄進不合適解資料庫並判斷原因，如果是邏輯拓撲規劃導致，則從新進行第四步，否則進行第二步
2.根據權利要求1所述.一種城軌列車網絡拓撲優化方法，其特徵在於，所述步驟(2)根據初始參數，生成初始基因並利用遺傳算法對節點間的物理連接方式進行規劃，具體步驟為: 假設G= (N，L, A)是一個沒有平行鏈路的網絡，並且網絡中沒有孤立點存在，受費用約束的網絡物理拓撲結構可靠性表述成為:
3.根據權利要求1所述.一種城軌列車網絡拓撲優化方法，其特徵在於，所述步驟(4)尋找網絡中任意兩個節點間的時延最小的通信方式，生成節點間邏輯拓撲規劃表，將列車通信網絡的邏輯拓撲優化表述為:
4.根據權利要求1所述.一種城軌列車網絡拓撲優化方法，其特徵在於，利用基因遺傳算法，雙層規劃求解過程如下: O求解物理拓撲優化模型 A.編碼方式 在雙層規划過程中，如何有效的將信息在兩層優化中傳遞，是非常關鍵的一個步驟，其中很重要的一點就是需要一個有效的基因編碼方式，基因編碼的第一步是確定基因的長度，對於一個有Nd個節點的列車通信網絡，其包含的鏈路數N1與節點數Nd之間的關係，可以用公式(9)表示，
【文檔編號】H04L12/24GK103716194SQ201310753028
【公開日】2014年4月9日 申請日期:2013年12月31日 優先權日:2013年12月31日
【發明者】董宏輝, 田寅, 賈利民, 秦勇, 馬慧茹, 滕志偉 申請人:北京交通大學