網絡交通流模型的建模方法
2023-05-28 01:48:16
專利名稱：網絡交通流模型的建模方法
技術領域：
本發明屬於系統科學領域，尤其涉及 一 種網絡信,l流交通系統。
背景技術：
近年來，以網際網路(Internet)為代表的信息技術的迅猛發展使人類社 會邁入了網絡時代。從Internet到WWW，從大型電力網絡到全球交通網絡， 從生物體中的大腦到各種新陳代謝網絡，從科研合作網絡到社會關係網絡， 這些人們身邊無處不在複雜系統都已成為科學研究中的熱點。1998年，美 國康奈爾大學理論和應用力學系的博士生Watts及其導師Strogatz在Nature 雜誌上發表文章，提出並建立了一個小世界網絡模型；1999年，美國聖母 大學物理系的Barabdsi教授及其博士生Albert建立了著名的無標度網絡。 這兩個奠定性的工作開創了一個十分引人注目的新興研究領域——複雜網 絡——的研究熱潮。
現代生活中，具有無標度特徵的大的通訊網絡如網際網路在人們的生活 中佔據越來越重要的位置。因此，複雜網絡上的各種動力學過程，例如信 息流的交通動力學問題，越來越受到研究者的關注。為了滿足人們對網絡 通訊能力不斷增長的需求，尋找好的路由策略成為了亟需解決的問題。現 在已有大量工作研究了網絡上信息流的交通擁堵問題，並且提出了很多較 優的路由策略，如局域路由協議、有效路由協議等。但以往的工作在為無 標度網絡上信息流交通動力學設計路由時，大多都是從均衡結點負載來提 高交通路由的效率。這些工作都忽略了信息包生命周期的限制，因此會造 成一些路由策略無效的環路過程，導致網絡的阻塞狀態。
發明內容
本發明的目的旨在至少解決現有技術中的上述問題之一 。
4為此，本發明的實施例提出 一種所建模型更加符合真實網絡的網絡交 通流模型的建模方法。
根據本發明的一個方面，本發明實施例的網絡交通流模型的建模方法，
包括以下步驟生成一個底層網絡；每個時間步在所述底層網絡中新增設
置有生命周期的信息包；在信息包被傳輸到鄰域中對應結點時將信息包的
生命周期進行遞減；將生命周期為零的信息包從所述網絡中退出。 根據本發明進一步的實施例，所述網絡為無標度網絡。 根據本發明進一步的實施例，在所述鄰域結點為目的結點時將信息包
從所述網絡中退出。
才艮據本發明進一步的實施例，在所述鄰域結點為非目的結點時依照以
下公式表示的優先概率傳輸信息包f],=^，2A。
其中i、 j表示所述鄰域內結點的編號，^表示所述鄰域中第f結點的連 接度，、表示所述鄰域中第7'結點的連接度，"為可調參數。
本發明建立的模型結合了真實網絡中的實際情況，對信息包附加了生 命周期的限制。考慮了信息包生命周期的限制以後，可以避免一些路由策 略無效的環路過程，消除了網絡的阻塞狀態。本發明的信息交通動力學模 型的建模方法考慮信息包生命周期，所得到的網絡模型更加符合真實網絡， 能夠較好地反映真實系統的屬性。
本發明附加的方面和優點將在下面的描述中部分給出，部分將從下面 的描述中變得明顯，或通過本發明的實踐了解到。
本發明的上述和/或附加的方面和優點下面結合附圖對實施例的描
述中將變得明顯和容易理解，其中
圖1為本發明實施例的網絡交通流模型的建模方法流程圖2為本發明實施例的底層網絡演化步驟流程圖3(a)到圖3(d)為本發明不同實施例的網絡模型的序參量-信息包產生 速率關係示意圖；圖4為本發明在不同生命周期下所建網絡模型中信息包平均數-連接度
關係示意圖5為本發明在不同生命周期下所建網絡模型的信息包平均傳輸時間
示意圖。
具體實施例方式
下面詳細描述本發明的實施例，所述實施例的示例在附圖中示出，其 中自始至終相同或類似的標號表示相同或類似的元件或具有相同或類似功 能的元件。下面通過參考附圖描述的實施例是示例性的，僅用於解釋本發 明，而不能解釋為對本發明的限制。
現在參考圖1,該圖顯示了本發明實施例的網絡交通流模型的建模方 法流程。
首先，生成一個底層網絡(步驟102)，例如無標度網絡(BA網絡)。 關於BA網絡的演化步驟的實施例可以參考圖2,例如生成一個網絡大小 # = 1000、每步增長的邊數^ =氣=5的BA (Barabdsi-Albert)網絡。
如圖2所示，首先生成一個具有氣個結點的全連通網絡(步驟202)。 每個時間步，產生一個具有m條邊的新結點,(步驟204)。在該實施例中， 可以按照以優先概率
選擇m個結點與新結點i連邊(步驟206),從而將這個新結點連接 到m個不同的已經存在於當前網絡系統中的結點上。在上述優先概率公式
中，^是網絡中第Z已有結點的連接度，、表示網絡中第y已有結點的連接 度，i、 j表示網絡中已有結點的編號，求和符號表示對網絡系統中所有已 存在的結點求和。
然後，判斷當前網絡中結點數是否達到指定的大小(步驟208 ),若 沒有達到預定大小，則重複上述步驟204和步驟206不斷地增加新結點， 直到網絡中結點個數達到預定的大小iV, BA網絡生成結束(步驟210)。
在得到底層BA網絡之後，每個時間步在該網絡中新增產生R個信息 包，隨機地選擇R個信息包的產生結點和目的結點，並對信息包設置一個生命周期(LC)(步驟104)。
在每個時間步裡，網絡中的結點處理自己隊列中的信息包(步驟106)。 假設每個時間步裡每個結點至多處理C個信息包。
然後，每一結點對其鄰域結點執行局域搜索，從鄰域中尋找正被處理 信息包的目的結點。即判斷目的結點是否在其領域內(步驟108)。若被 處理的信息包的目的結點在搜索範圍內，則將信息包直接送達到該目的地， 並且信息包從網絡中退出(步驟120)。
若鄰域中不存在被處理信息包的目的結點，則可以按照優先概率將 信息包傳送到鄰域中的一個結點i (步驟110)。優先概率例如以下面公式 表示
其中&表示該結點鄰域中第''結點的連接度，~表示鄰域中第7'結點的 連接度，"為可調參數，i、 j是鄰域內結點的編號，求和符號表示對於搜索 區中的所有鄰域結點的求和。從而將信息包傳送到其鄰域中的第Z結點。
然後，對網絡中所有信息包的生命周期進行遞減，例如均減一，即 LC二LC-1(步驟112)。接著，檢查每個信息包的生命周期大小是否為零(步 驟114)。若IXX),則將該信息包從網絡中退出；
否則，可以繼續判斷是否達到了指定的迭代代數(步驟116)。若終 止條件滿足，則結束循環，並得到相應的交通流模擬過程實驗數據(步驟 118);否則，返回步驟104，並重複步驟104到步驟116，直至滿足預定 的迭代條件。
基於上述步驟102到步驟118從而能夠建立一種考慮超時機制的基於 局域路由的信息流交通動力學網絡模型，從而本發明能夠模擬真實網絡交 通並得到相應的網絡性能數據。
圖3、圖4和圖5分別給出了對本發明建模方法得到的網絡交通流模 型不同實施例的分析，其對應的網絡特性示意圖。其中，圖3(a)到圖3(d) 為本發明不同實施例的網絡模型的序參量-信息包產生速率關係示意圖；圖 4為本發明在不同生命周期下所建網絡模型中信息包平均數-連接度關係示
7意圖；以及圖5為本發明在不同生命周期下所建網絡模型的信息包平均傳 輸時間示意圖。
序參量"用來定量地描述網絡的狀態，它的定義為
及Af ,
這裡C表示網絡中每個結點的處理能力，即每個時間步裡每個結點至 多處理的信息包數量，R表示信息包產生速率，A^=A^ + ")_^W, iVp(0
表示在時刻t網絡中的信息包的總數，表示在"的時間範圍內網絡中 信息包的變化量。當網絡沒有阻塞，每個時刻新產生的信息包和到達的信 息包的數目大致相等，處於一個平衡狀態，Mt0,因此"(W^。當網絡 陷入阻塞，網絡中的包會隨著時間不斷增加，從而使"(W)〉0。
由圖3(a)到圖3(d)可以看到，在沒有引入生命周期限制的條件下，即 LC-infmite (無窮)時，隨著信息包產生速率R的增大，網絡最終都會進 入阻塞狀態；而引入生命周期的限制後(例如LC二500 ),不論參數"取何 值("=-2.0、 -1.0、 0還是0.5),也無論信息包產生的速率R如何變化， 序參量"始終為0。這說明在對信息包設置有生命周期後，網絡不會進入阻 塞狀態，即阻塞狀態消除了。
現在參考圖4,在該圖中橫坐標k表示連接度，縱坐標n(k)是網絡中所 有連接度為k的結點所負載的信息包的平均值，即度為k的結點的信息包 平均數。如圖4所示，通過對網絡中結點的平均隊列長度，即每個結點處 等待處理的信息包平均數目做統計，從而由每個結點處等待處理的信息包 的進一步統計得到n(k)。
如圖所示，在加入生命周期LC的限制後，連接度為k的結點的平均 隊列長度n(k)隨著生命周期LC的減小而變小，有效地減輕了結點的負載， 從而消除了阻塞。並且，如圖所示，在不同的生命周期下，信息包平均數 n(k)與連接度k之間的函數關係基本保持不變。
如圖5所示，對到達的信息包的傳輸時間T做統計。隨著LC的減小，
間在網絡中逗留的信息包，使得信息包的平均傳輸時間T縮短。並且，由 於有了生命周期，接收一方就能確定其等待接受的信息包是否已經丟棄，從而及時作出有效反應，發出重傳信號或放棄接收。
本發明根據真實網絡中的信息包都有生命周期限制這 一 實際情況，提 出了 一種考慮超時機制的基於局域路由的信息交通動力學模型，引入了信
息包生命周期的概念。即，信息包在未達目的地之前不再一直停留在網絡 中，生命周期結束時自動從網絡中退出。
本發明建立的模型結合了真實網絡，尤其是無標度網絡中的實際情況， 對信息包附加了生命周期的限制。考慮了信息包生命周期的限制以後，可 以避免一些^^由策略無效的環路過程，消除了網絡的阻塞狀態。本發明的 信息交通動力學模型的建模方法考慮信息包生命周期，所得到的網絡模型 更加符合真實網絡，能夠較好地反映真實系統的屬性。
儘管已經示出和描述了本發明的實施例，對於本領域的普通技術人員 而言，可以理解在不脫離本發明的原理和精神的情況下可以對這些實施例 進行多種變化、修改、替換和變型，本發明的範圍由所附權利要求及其等 同限定。
9
權利要求
1.一種網絡交通流模型的建模方法，其特徵在於，所述建模方法包括以下步驟生成一個底層網絡；每個時間步在所述底層網絡中新增設置有生命周期的信息包；在信息包被傳輸到鄰域中對應結點時將信息包的生命周期進行遞減；以及將生命周期為零的信息包從所述網絡中退出。
2. 如權利要求1所述的建模方法，其特徵在於，所述網絡為無標度網絡。
3. 如權利要求1所述的建模方法，其特徵在於，在所述鄰域結點為目 的結點時將信息包從所述網絡中退出。
4. 如權利要求1所述的建模方法，其特徵在於，在所述鄰域結點為非 目的結點時依照以下公式表示的優先概率傳輸信息包其中i、 j表示所述鄰域內結點的編號，《表示所述鄰域中第^結點的連 接度，、表示所述鄰域中第y結點的連接度，"為可調參數。
5. 如權利要求4所述的建模方法，其特徵在於，"位於-2~0.5的範圍內。
6. 如權利要求1所述的建模方法，其特徵在於，所述底層網絡的生成 包括以下步-驟生成具有預定數量結點的全連通網絡；在所述全連通網絡上依次添加新結點並與已有結點進行連接，以得到 所述底層網絡。
7. 如權利要求6所述的建模方法，其特徵在於，根據以下公式表示的 優先概率，從已有結點中選擇預定數量的結點與每個新結點進行連接formula see original document page 3其中i、 j表示所述網絡中已有結點的編號，A表示所述網絡中第？已 有結點的連接度，、表示所述網絡中第y已有結點的連接度。
全文摘要
本發明公開了一種網絡交通流模型的建模方法，包括以下步驟生成一個底層網絡；每個時間步在所述底層網絡中新增設置有生命周期的信息包；在信息包被傳輸到鄰域中對應結點時將信息包的生命周期進行遞減；將生命周期為零的信息包從所述網絡中退出。本發明所建模型能夠消除網絡阻塞，更加符合真實的網絡。
文檔編號H04L29/06GK101651686SQ20091016906
公開日2010年2月17日 申請日期2009年9月17日 優先權日2009年9月17日
發明者曹先彬, 杜文博, 許言午, 陳才龍 申請人:中國科學技術大學