網絡中有效的路徑學習方法
2023-06-16 08:06:36
專利名稱：網絡中有效的路徑學習方法
技術領域：
本發明涉及一種方法和裝置，用來確定消息流通過由節點和互連通信鏈路組成的網絡的最佳路徑，具體而言，涉及這樣一種技術，它能夠讓這些節點高效率地確定最佳路徑，將必要的信息傳遞給相鄰節點，從而使它們也能夠確定它們各自認為的最佳路徑。
現有技術傳統的無線網絡中的節點一般都只在它們處於雙方通信範圍之內的時候才能夠進行通信。建築物和山、山谷這樣的地形會影響無線網絡中各種節點的通信範圍。另外，改變每個節點的通信量和其它因素會在節點之間形成業務分配的問題。不僅在無線網絡中會碰到這些通信問題，在其它類型的網絡中也會碰到。
一般都需要複雜的軟體協議來控制消息的傳遞，從而能夠從一個小區到另一個小區進行通信。這些協議一般都會給網絡通信信息增加大量的系統開銷。還有，為了保證有足夠的通信範圍，這些系統一般都需要每個節點都有較高功率的發射機以便和網絡中的全部節點進行通信。但是，即使使用較高功率的發射機，通信也有可能在源節點、目標節點或者通信鏈路發生故障的時候中斷。此外，這些系統還受限於從源節點到目標節點的距離和方向，結果，必須周期性地向網絡中的所有節點發射複雜的路由選擇信息。顯而易見，發射的路由選擇信息涉及到網絡中所有節點的時候，這一信息量非常大，導致網絡沒有足夠的資源來完成它傳送通信信息的主要任務。
在無線網絡中路由選擇協議領域有大量的工作需要做。在事先不了解有什麼節點的小型到大型網絡中，傳統系統只通過「IP位址」確定的節點來解決這一路由選擇問題。有關的路由選擇協議試圖獲得從源到目的地的一條路徑進行數據分組通信。可以將這樣的無線網絡劃分成兩大類蜂窩網和ad hoc網。
今天正在發展或者正在標準化過程中的多數無線聯網技術是想提供無線裝置來訪問大型，常常是有線的網絡。這種設計能夠給希望訪問公共網，比如網際網路，以及專用網的那些用戶帶來無線自由和漫遊的好處。同樣，考慮無線終端被當作有線網絡擴展的設備的層次結構。在蜂窩網絡中，區域內散布著一些特殊節點(一般都叫做基站)。這些「特殊節點」能夠通過有線網絡、衛星、更高的發射功率等等互相通信。正常情況下發射功率較低的用戶與這些節點中的一個節點通信。如果需要與其它無線節點通信，就通過其它特殊節點交換消息數據。但是需要注意幾個協議，比如這些節點在什麼地方，當這些節點從一個小區移動到另一個小區的時候會發生什麼事情。IEEE 802.11無線LAN標準這樣的標準定義了一些接入點，它們負責將無線終端發射過來的信息傳遞給其它類型的傳輸網絡，包括有線、無線和光學的。這些接入點負責管理它們所在區域中的無線終端，控制是否允許進入網絡，還控制著本地的發射時序。接入點必須與它所在區域的每一個無線終端直接通信，工作起來有些象蜂窩網絡中的基站一樣。
另一方面，在ad hoc網絡中，沒有已知的任何特殊節點。這些網絡並不特別需要另一個網絡支持，但是需要希望互相通信的一群無線裝置互聯。要傳遞的數據可以來自一個或者多個所述裝置，也可以來自通過一個或者多個節點與這個無線網絡連接的另一個網絡。這些節點構成的網絡必須首先真正建立起網絡。這些節點交換消息，從而找到相鄰節點，以及獲得相鄰節點的其它信息。一些協議需要在這些信息的基礎之上頻繁地交換節點位置、鏈路等等信息，所有節點都試圖保持到網絡中所有其它節點最新最佳的路徑信息。其它協議集不保存最新路徑信息，但是一個源節點需要與一個特定目標通信的時候，就會搜索這個目標節點。多數協議都會建立在保證這一路徑上中繼次數最少和這一路徑上的時間延遲最短這樣一個基礎之上。這些協議都對具有不可靠通信鏈路的網絡中，最佳路徑常常不是最短路徑這樣一個事實感到頭疼。最短路徑方法通常都選擇距離最長的單條通信鏈路，而這些鏈路一般都是最不可靠的，需要數不清的重新發射，才能將數據組從一個節點可靠地傳送到下一個節點。
發明目的需要一種通信系統，它具有簡單的軟體協議用來控制消息的傳遞，它足夠簡潔，不需要給通信系統增加很多的系統開銷。這些協議還應該支持ad hoc無線網絡中節點之間的ad hoc通信，而不需要考慮網絡中其它成員特別是目標節點是否鄰近。本發明能夠根據多個參數選擇路徑，它比僅僅通過評估從源到目的地總的通信費用，使中繼次數最少或者路徑延遲最小這樣一個路徑選擇方法要好得多。
在現有技術網絡中，每個節點都試圖獲得網絡中每個其它節點的信息。這些信息會給系統資源帶來負擔。隨著網絡中節點或者其它參數增加，每個節點處理的信息會按照指數規律增加。在本發明中，信息不會按指數方式增長，增加新節點或者其它參數只會使得需要的信息線性增加。
發明簡述本發明涉及網絡，最好是用通信鏈路互相連接的網絡節點的自我管理網絡。不需要所有節點都能夠互相直接通信。相反，每個節點都能夠確定從它自己到儘可能多的其它節點的直接的或通過其它節點中繼的通信路徑或者路由，從而使這一網絡完整。產生有關路由的新信息的時候，按照選定的判據評估這些路徑，從而找到、記住並且在通信的時候使用最佳路徑。本發明涉及如何確定通過網絡的最佳路徑，以及在通信狀況和節點數量發生變化的時候如何維護這些路徑這樣一些問題。
確定最佳路徑的方法在每個節點內採用相同的算法，該算法從每個節點的角度解決路由選擇問題。有多個節點的時候，通過網絡從一個節點到遠處的某個節點一般都有許多條路徑。在本發明中通過網絡的最佳、次佳和第三佳路徑的選擇是通過選擇讓選中的費用函數最小來做到的。費用函數由任意多個度量組成，它們被按照特定網絡的目標來定義。這些度量可以包括但不限於消息到達目標節點之前必須通過的節點的數量、成功通過一條路由的概率、在這個路由的一段中成功傳輸的最小概率、網絡中每個節點的通信負擔等等這樣的參數。
根據用戶的選擇，本發明一般都可以採用兩種度量以及它們的變型，各個參數到發射類型的加權重要性。例如，一組參數可能對於確定話音通信的最佳路徑更加重要，另一組參數與數據通信聯繫更緊密。第一種度量通過選擇一個參數，針對路徑上單個最弱或者單個最佳點，確定給定路徑是不是最佳路徑，來評估路徑。第二種通過確定從源到最終目的地的整個路徑的質量度量，根據傳輸是否具有整體最佳值，來評估路徑。第一種度量的一個實例可以是確定路徑上最擁擠的節點或者傳輸成功概率最高的節點。第二種的一個實例是計算路徑上的中繼次數。第二種的另一個實例是為選中的一組參數中的每一個確定一個值，根據每個參數的相對值進行加權計算，從而確定路徑上的最佳路由。本領域中的技術人員會明白，在確定任意給定時刻最佳路徑的時候，這些參數或者選中的參數可以象給予每個參數的權一樣改變。
不論採用哪一種度量或者它的變種，選擇從源節點到最終目標節點最佳路徑必需的所有信息最好是只是通過從與源節點直接通信的節點了解。這是因為作為源的任意節點都只能夠跟它的相鄰節點通信。這樣，最初的源節點必須選擇到最終目的地最佳路徑上的相鄰節點。最佳路徑的確定建立在選中的參數這一基礎之上。鏈上到目的地的第一個節點選擇取決於每個節點根據從相鄰節點收到的信息，計算到網絡中其它每個節點的最佳路徑產生的數據。一旦消息通過，最初的源節點就不會對消息路徑產生進一步的影響。在這一點上，選中的相鄰節點成為消息的新源，而最終目的地保持不變。這個相鄰節點重複最初的源進行的路徑選擇過程。這一過程重複下去，直到消息到達最終的目標節點。
得到的用於選擇路徑的信息最好是保存在每個節點中的一個表內。表中的每一行都用最終的目的地做索引，每一列都包括這個節點為到達所述目的地的路徑計算的具體度量。放進節點的表中的信息通過處理來自每個相鄰節點的表的信息而加以確定。本發明中這一過程的一個實例如下。假設路徑的費用由兩個度量組成，路徑上最擁擠的節點上等待傳送的消息的數量，以及從源到目的地的中繼次數。通過定義路徑的最終目的地，(路徑上消息計數度量或者它自己的消息計數)的最大值，最佳路逕到最終目的地上中繼的次數，將這些度量從一個節點傳遞給相鄰節點。接收節點將中繼次數增加1，從而將相鄰節點作為另外一次中繼，並且計算利用這兩個度量通過這個相鄰節點傳遞到最終目的地的費用。將它與為這個目的地的最佳路徑儲存的費用進行比較，根據選中的新的最佳路徑刷新這個表。
可以將度量作為單獨的信息發射給相鄰節點，也可以與正常傳遞的消息業務並置傳送。在單獨的消息中發射度量的時候(比如存在一個廣播信道的時候)，傳遞用戶消息的時候，系統開銷通常都受限於網絡源或者通信的始發節點、鏈路源和這一通信的鏈路目的地以及這一通信的網絡目的地。也可以在消息傳遞量較低的時候，或者得到相鄰節點特殊請求的時候，用專用消息發射。按照本發明將度量發射給相鄰節點的時候，將一個或者多個表格行放到消息內。選中的行最好是按照它們最後一次傳送的最後刷新時間排定優先級。這樣就能夠加速新信息通過網絡的流通。消息可以傳遞給一個特定的相鄰節點，但是可以被所有相鄰節點同時看到。所有相鄰節點最好是將表格行信息作為廣播信息接收，據此處理它而不管指定作為消息其餘部分的下一個目的地的相鄰節點。
利用本發明的方法，一個節點選擇要將消息發射過去到達某個最終目的地的最佳相鄰節點。這一節點根據能夠獲得的所有信息來選擇這第一個中繼節點。消息傳遞的問題現在就落到了選中的相鄰節點的頭上，這一過程重複下去。短路徑顯然沒有什麼問題。對於涉及多個中繼和不可靠通信鏈路的長路徑，這一路徑可能隨著消息的傳遞過程而發生改變。這一點對於最初的節點而言並不重要，因為它得不到這一信息。重要的是消息從正確的方向開始，消息通過網絡的時候，它的路徑會連續不斷地優化。當它到達最終目標節點附近的時候，消息經過的這條路徑上的節點就會已經學習並且刷新了它們到達目標節點的路徑信息。
附圖簡述
圖1是通過網絡的路徑的一個實例。
圖2是幾個鏈路費用函數的一個圖形比較。
圖3說明相鄰節點之間的通信路由信息。
圖4是「十字叉」情形的一個說明。
圖5是一個流程圖，它說明確定最佳路徑時節點所用步驟的一個實例。
圖6是一個流程圖，它說明根據從它的一些相鄰節點收到的信息為一個節點刷新路由表的一個實例。
優選實施方案網絡節點如同本領域中所用到的一樣，本發明中的網絡可以是任意網絡，包括但不限於LAN、WAN、網際網路、衛星通信系統、地面通信系統等。這裡使用的節點這個術語可以包括但不限於蜂窩電話、基站、軍事基地等。本發明的節點應該具有計算能力、存儲器，並且能夠與一個或者多個其它節點通信。本發明的一個優點是節點的計算能力不必非常強。在許多情況下，甚至8比特的處理器就能夠為本發明的實踐提供足夠的計算能力。通信能力可以是任何一種形式，包括但不限於無線電、光纖網、有線方式等等。
在這裡定義的網絡中，節點的功能類似於分組交換的功能，能夠自動地建立和維護好一個分組通信網絡。每個節點都可以有幾個輸入信道和幾個輸出信道，可以用例如頻率、時隙或者擴頻碼來定義它們。節點將維護通過通信鏈路到其它節點的輸入和輸出信道。
由於數據包不必按照收到它們的時候的樣子發射，因此可能必須將它們儲存起來，至少要等到可用的下一個發射時隙。一般都要將它作為等待隊列積累。此外，由於通信鏈路不是100％可靠，因此可能需要它們重新傳送沒能到達下一節點的數據包。這些數據包將被儲存在例如重發隊列中。最好是分別維護兩個不同的隊列，從而在需要的時候可以將等待重發的數據包作為不同於新數據包的數據包對待。一般情況下，在隊列和輸出信道之間沒有任何固定的分配關係。在數據包選擇過程中，任意數據包都能夠競爭任意信道。本發明的節點最好還有等待隊列和重發隊列。
能夠接收另一個節點發射的數據包的節點都被看作那個節點的鄰居或者一個相鄰節點。圖1給出了某個地區分布的許多節點的一個實例。節點用圓圈表示。用有兩個箭頭表示雙向通信的線段表示通信鏈路。弱的或者很少使用的鏈路用虛線表示。在這個實例中，節點F有相鄰的一組節點B、C、E、G、I和J。網絡中的節點數量可以是保持靜態不變，也可以隨時間變化。節點可以物理上進入和離開這個區域，可以因為例如電池電壓過低或者電池電力消耗完畢而不能發出功率，可能因為結構、地形或者其它東西的幹擾等等而丟失到另一個節點的無線電鏈路。當節點物理上在一個區域內到處移動的時候，或者通信狀況發生改變的時候，這個節點的相鄰節點清單會發生改變。節點只能通過它們的相鄰節點集中的一個或者多個成員發射消息，與它們的相鄰節點集以外的節點來進行通信。與相鄰節點集以外的任意數量的節點的通信都能這樣進行。
給定節點進行路徑選擇的第一步是了解它相鄰節點集的組成及其成員的通信能力。一旦完成這一工作，就可以通過發射一則消息給適當的相鄰節點對該系統中的任意節點尋址，這個節點會將這一消息中繼給最終目標，或者中繼給到最終目標的路徑上的另一個節點。圖1說明從一個節點到另一個節點能夠用的幾條路徑。這個圖還說明這些路徑可以具有不同的長度(中繼次數)和不同的質量(成功地與目標通信的概率)。每個節點都可以學習通過網絡的各種路徑，並且根據選定的判據評估路徑質量，從而為每次通信選擇最佳路徑。例如，假設節點H需要發射一則消息給節點M。這一消息可以直接發射，也可以通過節點K中繼。中繼方法需要使用更多的通信鏈路，但是由於這些鏈路質量更高，因此有可能成功的概率更高。對於更高鏈路質量更加重要的一些應用，比如數據通信，通過節點K的路由最好。對於鏈路質量不那麼重要的其它通信，從節點H到節點M的直接路由最佳。鏈路質量不是那麼重要，但是中繼次數較少比較重要的一個實例是話音通信。因為要求延遲最短，所以話音通信一般都希望中繼次數最少。
支持學習和路由判決必需的信息的通信是一個網絡系統開銷功能。由於每個節點都只有它相鄰節點的信息，因此使用的網絡系統開銷資源較少。
自動路由選擇最佳通信路徑由自動路由器確定，它可以是軟體的形式，也可以是固件的形式。最好是每個節點都有一個自動路由器。自動路由器根據來自相鄰節點的信息，確定通過網絡從給定節點到一個相鄰節點，最後到達目標節點的最佳路徑。本發明將最佳路徑定義為使得通信總費用最小的路徑。這一費用可能有幾個組成。雖然圖中畫出了幾個組成，但是本領域中的技術人員會明白還有其它的組成可以根據通信類型加以使用。另外，給予每個組成的權可以根據應用改變，也可以在同一個應用中隨著時間改變。
將會看到在路徑上的單獨一條鏈路上傳遞一則消息的費用正比於成功地將消息傳遞給下一個節點之前，這個節點上消息發射的平均次數。自動路由器根據從相鄰節點收到的信息確定整條路徑的總通信費用。
消息費用是通過網絡傳遞消息的時候將消息避開當前有許多消息等待轉發的節點的一種手段，避開這些繁忙節點的時候需要它。消息費用為馬上就要將當前儲存在這個節點的消息傳遞給後續節點的通信成本有多高提供一個估計。根據從相鄰節點或者目標節點收到的信息，此時這個目標節點就是一個相鄰節點，自動路由器為這個特定節點到最終目標節點的整條路徑評估這一參數。
存儲器使用率和處理器負擔費用提供了一些手段來避免這些節點給可用存儲器或處理器的計算能力施加的負擔過重。存儲器使用率參數決定了支持計算和通信任務所需要的可用存儲器的百分比。這個處理器負擔建立在這個節點上當前正在執行的任務所需要的計算時間這個基礎之上。
消息計數和優先消息計數參數提供一條路徑上消息總數的一種直接度量，以及優先消息的單獨計數。這些參數說明將消息傳遞到下一個節點的過程中，路徑節點馬上就要變得有多繁忙。
另一個費用是路徑延遲，它隱含在鏈路計數參數中。這個參數是將消息從當前節點傳遞到最終節點所需要的單條通信鏈路的數量。
網絡自動路由器利用單個節點的參數來確定每條路徑的總費用。於是將當前節點到目標節點的最佳路徑選擇為具有最小費用的那條路徑。自動路由器能夠有效工作的中心思想就是每個節點都能夠從它的相鄰節點獲得做出這一判決所必不可少的信息。這樣，一個節點必須只確定最佳路徑上的最佳相鄰節點，然後把信息傳遞給這個節點，在這個節點中重複同樣的處理過程。這樣一種思想能夠解放所有的節點，它們不再需要知道到目標節點的最佳路徑上所有節點的身份，從而騰出系統資源用作其它用途。
如上所述，可以用兩種基本方法中的一種來評估任意網絡路徑。一種方法是將路徑上所有節點的相似參數結合起來評估這些參數。第二種方法是通過針對給定參數找到路徑上的最差節點或者最佳節點來評估路徑。於是，第一種方法是評估整條路徑的能力，而第二種方法則只根據它的最弱或者它的最佳鏈路來評估這一路徑。
可以按照第一種方法來評估通信費用。這是因為被評估的參數表示將消息從它的始發節點向目標節點移動的網絡總費用。每個節點都評估將消息從它自己傳遞到路徑上下一節點的費用。傳遞這一消息的總費用被定義為路徑上每條鏈路的通信費用總和。為了確定從始發節點到目標節點每條路徑的這一參數，只需要所有節點將從它們自己到每個可能的目標節點的費用告訴給它們的相鄰節點。由於這些節點要通過網絡傳遞，所以總路徑費用被新的信息更新，直到所有節點都知道所有路徑的這一參數值。這樣，如果B是A的一個相鄰節點，Z是目標節點，B必須向A傳遞從B到Z的通信費用信息。A知道從A到B的通信費用，會將這一費用與從B到Z的通信費用加起來，確定通過節點B從A到Z的通信費用。
用同樣的方式將鏈路計數參數累加起來。最終的最佳路徑選擇將建立在所有單個費用構成的加權和這個基礎之上。每個參數的權由用戶確定，用戶要考慮每個參數對於通信的重要性。
消息費用是這樣一個參數，它決定了傳送當前儲存在這個節點中的所有消息所需要的通信費用。同樣，這個參數是確定消息傳遞過程中不需要的節點的一種手段。這樣，第二種方法可以被用來評估一條路徑的消息費用。在這種情況下總的路徑消息費用可以被定義為這條路徑上每個節點消息費用的最大值。這樣，一個節點會從相鄰節點接收通過所述相鄰節點的路徑的消息費用。這一路徑的總消息費用可以在相鄰節點計算出來，因為它具有評估路徑消息費用的所有信息。利用上面的A-Z實例，B是知道沿著從B到Z的路徑的所有消息費用最大值的那個相鄰節點。B還知道節點B的消息費用。這樣，B能夠確定從B到Z包括B的所有節點的節點消息費用的最大值，它就是從A到Z的消息費用。由於A是被考慮的這條路徑上的起始點，所以從A出發選擇路徑的路由選擇判決過程中不需要考慮它的消息費用。同理，由於Z是通信的終點，Z的消息費用同樣不是確定這個參數的一個因素。
與消息費用的方式相似，針對各種網絡路徑評估處理器負擔、存儲器使用率和消息計數參數。於是，計算這些路徑費用的加權和作為路徑的總費用。每個節點都會隨後記住到所有可能目標節點的幾條路徑作為最小總費用路徑。幾條路徑能夠為避免將來的路徑或者節點發生故障而提供一些選擇。
本發明的自動路由器的性能明顯優於現有技術中典型的最短路徑算法。作為一個實例，假設在路徑選擇中只使用通信費用這一信息。選擇具有最少鏈路數的路徑的最短路徑算法(比如US6130881和US5142531所介紹的那種)始終存在一個大問題。如果能夠用一條鏈路從A傳遞到B，用一條鏈路從B傳遞到C，它們都只傳送一次，但是A傳送到C一般都需要傳遞三次，那麼最短路徑算法總是會嘗試直接從A傳遞到C。本發明的最佳路徑算法將給A-C路徑計分3，將A-B-C路徑計分2，選擇A-B-C路徑，因為需要的傳送次數最少。這樣就能夠清楚地解決將所有鏈路拉伸到斷點這樣一個問題，這個問題是使用最短路徑算法的一個典型問題。
最佳路逕自動路由選擇算法儲存和轉發網絡中同時存在許多不同的過程。有幾個節點在不同的點通過網絡進行通信，而其它節點則接收數據，或者對大量數字進行處理。自動地為消息選擇通過網絡的路由的最佳路徑算法必須考慮通信鏈路狀況和網絡節點狀況。做出路由選擇決定的時候需要權衡各種網絡參數。
將最佳路徑定義為按照網絡中每個參數的相對值，從始發節點到目標節點之間具有最小網絡費用的那條路徑。算法的最佳路徑處理是確定網絡費用的一個函數。優化結果是給不同網絡費用組成進行加權處理的一個函數。
網絡費用將消息從始發節點傳遞到目標節點總的網絡費用一般都可以劃分成四個主要組成部分。但是，本領域中的技術人員都知道在一些應用中可能需要其它的組成部分，或者需要減少一些組成部分。在這個實例中，這四個組成部分是通信費用、增大了的消息量的網絡負荷、一個節點上額外消息的存儲器存儲費用和通過繁忙節點或者鏈路的消息延遲費用。
為了給通過網絡的消息選擇最佳路徑，需要儲存和轉發分組網絡中始發節點到目標節點的一整條路徑上的通信費用。為了使網絡實際可用，網絡費用的評估必須用一種比較簡單的方法完成。如同下面所討論的一樣，有一些切實可行的方法可以用來估計計算網絡費用必不可少的鏈路和節點參數。於是，最佳算法就是確定從單條鏈路的各種路徑的網絡費用和節點費用。
在下面的討論中注意到網絡費用的計算是在每個節點上完成的，並且傳遞的信息和儲存的信息是每個節點專用的這一點是非常重要的。得到的算法完全分布在整個網絡中每個節點的自動路由器裡。每個節點都記住它做這項工作需要什麼，除此以外不去記更多的東西。一般情況下，沒有任何節點知道任何一則消息通過網絡會通過哪一條路徑(除了只有一條鏈路的路徑以外)。
通信費用從任意節點j發射消息所需要的能量是發射消息的時候的通信費用。這個費用是消息長度的函數，記為cj(M)。在要到達的目標節點k正確地收到消息的時候，這個節點要發射一則收到確認消息。費用是收到確認消息長度的函數，記為ck(A)。通過這條鏈路在j和k之間發射這一消息的網絡費用為cjk＝cj(M)+ck(A)其中為了簡單起見去掉了費用對消息長度明顯的依賴性。
如果沒有正確地收到消息或者收到確認，網絡費用就會增大。不管什麼時候出現這種情況，發射-收到應答過程會重複進行。將鏈路上從j到k成功地完成發射-收到應答過程的概率記為Pjk。於是不成功必須重複的概率為1-Pjk。於是，從j向k發射一則消息的總的平均費用可以寫成Cjk＝cjk+(1-Pjk)cjk+(1-Pjk)2cjk+(1-Pjk)3+…+(1-Pjk)N-1cjk其中N是為了另一操作拋棄這個過程之前通過鏈路j-k所作的通信嘗試次數。如果將這另一操作的費用表示為Ajk，那麼從j到k的通信嘗試，不管是成功還是不成功，的網絡平均費用為Cjk=n=0N-1(1-Pjk)ncjk+(1-Pjk)NAjk]]>可以將它寫成簡化形式Cjk=1-(1-Pjk)NPjkcjk+(1-Pjk)NAjk]]>當N次通信嘗試失敗的時候，需要的操作的額外費用值的一個合理假設是Ajk＝Cjk。這個假設基本上是通過嘗試將消息傳遞到不是k的另一個節點，節點j能夠恢復。到達這另一個節點的這條鏈路可能比到達節點k的鏈路好或者差，但是這一點很可能將在長時間內被平均掉。利用這一假設，鏈路發射的網絡費用可以被寫成Cjk=cjkPjk]]>將把這個方程叫做鏈路費用方程。
圖2畫出了四條曲線，它們的相互關係說明推導出鏈路費用方程的時候涉及的概念。為了簡單起見，讓費用Cjk等於1。鏈路費用方程被看作圖示其它三條曲線的上限。這些曲線是用以下方程畫出來的Gjk(N)=1-(1-Pjk)NPjk]]>它表示通過這條鏈路成功通信的網絡費用，不包括校正操作額外的費用。針對N的三個值畫出了這些曲線。當鏈路成功概率較高的時候，所有三條曲線都相同，因為成功通信，很少重複發射的可能性非常高。當鏈路概率下降到0.5以下的時候，那麼N＝5的曲線就與其它曲線分開了，因為有五次嘗試的失敗可能性非常大，在這條曲線中沒有任何失敗費用。鏈路概率較小的時候，N＝10和N＝20對應的曲線也會有同樣的現象。
圖2說明鏈路概率的值，在這裡失敗成為了重要的費用項。假設在鏈路邏輯中將採用N＝5這個值。利用這個值，在鏈路成功概率低於0.5的時候，失敗開始明顯。這一點的失敗概率是大約0.03。
消息費用路徑上的節點常常儲存有能夠發射的一組消息。它們可能是這個節點上的任務產生的消息，它們也可能是將這個節點用作某條路徑上的一個中繼站的消息。如果消息沒有分布在各個節點上，有效地處理通信的網絡能力會下降。一個節點上儲存的消息的量會影響通過這個節點的路徑的選擇。
將一個節點中儲存的所有消息發射出去的網絡費用可以按照以下方法確定。假設節點j有M則消息儲存在它的存儲器中等待發射。對於每則消息，確定發射到它路徑上下一個節點的鏈路成功概率。這些發射中每一次的費用由鏈路費用方程確定。假設發射費用與消息長度和收到確認消息的長度無關。於是，鏈路費用方程中的分子是一個常數，可以將它設置為等於1。於是，可以將消息費用寫成Mj=k=1M1Pjk]]>將它叫做消息費用方程。這個方程給出了將一個節點當前儲存的消息傳遞出去的通信費用的一個估計。這個費用是短期發射它儲存的消息的過程中這個節點要花費的時間的一個直接函數。於是，消息費用方程為這個節點的短期通信工作負荷提供了一個信息。
如果在一個節點上沒有任何消息在等待，就將這個消息費用定義為0。否則，這個消息費用就會是至少與節點中儲存的消息數量一樣大的一個數。消息參數是應用於一個節點的單獨一個參數。當消息通信很少的時候，這個參數的值會隨著進來的每則消息快速改變。平滑消息費用參數，防止它的值快速起伏是有益的。這樣做還有將一些過去的歷史結合到這個參數中去的額外好處。通過這種方式，最近的歷史中有過過量通信工作負荷的那些節點。
既然消息費用的下限是消息的數量，這個量就可能特別大。實際上針對向相鄰節點發射信息計算出來的最佳參數是平均消息費用。消息費用可以通過將平均費用乘以儲存的消息的數量加以確定，這個消息數量可能是發射的另一個狀態參數。
工作負荷費用計算負擔過重，或者正在執行需要大量存儲器的任務的那些節點，在可能的時候應當給它們較少的通信負擔。
叫做複雜程度的參數與每個處理器的任務類型有關。說明任務的計算負擔，以便估計給定節點處理器負擔的時候，複雜程度是有意義的。這個參數由給這個任務的代碼編程的人來確定，可以是其它任務參數的函數。
在每個節點中這個自動路由器有一個作業系統，它會掃描正在執行的任務，確定下一步執行哪一個任務。在這一操作過程中，使用這一作業系統的自動路由器將這些複雜程度值累加起來。一旦累加起來，得到的和就給出了處理器負擔的一個短期估計。可以對這個值進行平滑，去掉快速起伏。得到的結果是處理器負擔的一個估計，被用作工作負荷費用估計的一部分。
存儲器使用率可以通過對隊列中使用過的記錄的數量進行計數來確定。結果是隊列使用率的一個估計。在時間上平滑這些值會得到隊列百分比使用率的估計，它對於消息路由選擇而言足夠精確。
延遲費用消息路徑需要考慮總的路徑延遲。反向路徑只需要選擇成能夠避開會導致將消息傳遞給目的地所需要的時間加倍的繁忙節點就可以了。對於一些消息，這樣做是完全可以接受的，但是有許多情形，比如優先消息，這樣做則是完全不能接受的。只針對最低優先級以上的消息考慮延遲費用。這樣就能夠在可能的時候允許優先消息，如果不是鼓勵的話，離開主流消息通信流。
延遲費用的這兩個組成是從始發節點到目標節點的路徑上鏈路的數量和這條路徑上節點裡當前儲存的優先消息的數量。它說明它有點正比於將消息傳遞給它的最終目的地所需要的時間。
一條路徑上鏈路的數量取決於來自相鄰節點的信息。將鏈路參數累加起來，和正常通信信息一起傳送。優先消息的數量按照確定鏈路數量的方式來確定。它們都是路徑的參數，能夠反映優先消息在這條路徑上的時間延遲。
總的網絡費用將節點j到節點m之間的路徑P上進行通信的總網絡費用表示為上述費用組成的加權和。可以將這個費用寫成Np=a1Ll1Pl+bmaxj(Mj)+cmaxj(Bj)+dmaxj(Gj)+eL+flCj]]>其中l的變化範圍包括了路徑P上的L條鏈路，j表示路徑P上的節點，Bj表示節點j的計算負擔，
Gj表示節點j上的存儲器使用率，Cj表示節點j上優先消息的數量。
將消息沿著可用路徑上具有最小Np的節點傳送。
路徑P的網絡費用加權和允許網絡或者用戶或者這兩者通過控制a到f的權來控制各種路徑、鏈路和節點參數的影響。這些權可以是動態的，因此選擇路徑所用的邏輯可以隨著網絡狀況的改變隨時間改變。還有，不同節點上的權可以不同。由於在通信問題不同的區域存在不同的節點，所以每個節點都可以按照最適合它自己的方式優化路徑選擇邏輯。這樣，a到f的權可以與時間和節點有關。
網絡費用評估一則消息通過網絡到達它最終目的地的「最佳路徑」可以通過選擇使得總的網絡費用Np最小的路徑來加以選擇。加權係數的調整決定了任意給定條件下「最佳」這個術語的含義。例如，網絡最初形成的時候，不需要明確地使用節點存儲器，也不需要明確地在節點隊列中構建消息。「最佳路徑」將是通信費用最小的路徑。網絡工作了一會以後，可能給了一些節點繁重的計算負擔，一些節點可能成為消息瓶頸。在這種情況下，使通信費用最小沒有比避開因為這個原因或者那個原因而負擔繁重的節點那麼重要。這個簡單的實例說明網絡的「最佳路徑」取決於當前的情形，因此，「最佳路徑」是隨著時間改變的。這就意味著網絡必須不斷地適應每個節點狀況的變化。因此，不可能針對所有節點和路徑解出總網絡費用方程，將得到的解應用於所有節點，然後聲稱這個問題得到了解決。
考慮到每個節點的狀況是在不斷變化著的，它意味著通過網絡的這一組「最佳路徑」也是在不斷地變化著的，就需要一種方法來學習和更新每個節點上儲存的「最佳路徑」，以便得到切實可行的網絡。為了獲得最佳路徑算法，考慮由N個節點構成的一個網絡。檢查一個典型的節點j，很清楚節點j有m個相鄰節點，其中0≤m＜N，相鄰節點是能夠從節點j進行直接通信的任意節點。如果選中的節點是m＝0，就將它從網絡中隔離出來，它不能與任何其它節點通信。如果選中的節點是m＝1，那麼它所有的通信信號就必須通過這一個可用相鄰節點，才能到達任意目標節點。儘管這些概念看起來微不足道，但是它們指出了這樣一個事實，那就是總的來說任意節點的通信能力受到它相鄰節點的通信能力控制。事實上，從我們的節點到任意其它節點「最佳路徑」的選擇不過就是選擇這條「最佳路徑」上的那個相鄰節點，然後將消息傳遞給那個相鄰節點。於是相鄰節點就會從它的角度評估所有路徑，確定它的相鄰節點中哪一個相鄰節點處在到達最終目的地的「最佳路徑」上。這樣一來，從始發節點確定的「最佳路徑」可能不是它的第一個相鄰節點評估出來的那條路徑，因為狀況可能發生了改變，而這一信息還沒有傳遞到始發節點。
始發節點從它的觀察角度選擇「最佳路徑」，因此是根據所有可用信息來選出最佳路由的。在實際的消息路徑上每個節點裡都進行同樣的操作。如果網絡是靜態的，所有節點的所有信息都是當前的，那麼始發節點選出的「最佳路徑」就是實際使用的路徑。在實際應用中不一定是這種情形，但是無關緊要。每個節點所作的選擇將是相同的，而不管以後在這條路徑上所作的選擇如何。這樣，選擇到達最終目標的「最佳路徑」上相鄰節點中的下一個節點的節點根本不需要了解這條消息的實際路徑。相反，這個節點將根據從它的每一個相鄰節點到消息目的地的路徑的選擇做出判決。
節點確定到目的地的「最佳路徑」上相鄰節點所需要的信息包括兩個明顯不同的部分。第一個部分是評估從這個節點到相鄰節點的通信鏈路。第二個部分是從這個相鄰節點到最終目標的路徑的評估。學習算法涉及允許每個節點選擇到任意所需目標的「最佳路徑」上相鄰節點的路由選擇信息的傳遞和處理。這個算法可以假設任意節點需要的所有信息都保存在它相鄰節點的存儲器中。如果這一信息不完全是當前信息，那麼它就是能獲得的最新信息，在每個節點進行學習的時候進行刷新。每個節點進行學習的時候，重新執行這一算法，更新路由選擇表中的這些信息。
這裡給出的學習算法利用例如通信費用參數。可以用同樣的方式更換成總網絡費用方程中的所有其它參數。在這個學習實例中，將鏈路k到它相鄰節點j的鏈路的通信費用表示成Cj，k。將節點j到節點N的平均通信費用(路徑上所有鏈路費用的和除以路徑上的鏈路數量)表示成Aj，N，節點j和節點N之間的鏈路數量表示成Lj，N。如果節點k知道到它相鄰節點j的鏈路的通信費用，還知道從j到目標節點N的通信費用，那麼這個節點就能夠利用以下方程評估從它自己到N的通信費用Ck，N＝Ck，j+Aj，NLj，N其中從k到N的通信費用是到相鄰節點Ck，j的鏈路費用，以及從相鄰節點到目標節點N的通信費用之和。
圖3畫出了一個網絡實例，其中目標節點N位於網絡中的某個未知位置。節點i是節點j的一個相鄰節點，對到達節點N的路徑進行了評估。這一評估的形式是每條鏈路的平均通信費用Ai，N，鏈路數量Li，N，並且將它傳遞給節點j。節點j利用這一信息，並且將它的費用評估傳遞給節點i，為j到N的路徑確定評估參數。
節點j將路徑評估參數傳遞給節點k和m。這些節點在不間斷地評估到節點j的通信費用。這樣，在任意時刻，這些節點都能夠計算通過節點j到節點N的通信費用。節點k還要將它到達節點N的路徑的評估結果傳遞給節點m(m做同樣的事情，並且發射給k，但是為了簡單起見圖3中沒有說明這一點)。這樣，不管什麼時候節點m需要發射一則消息給節點N，它都能評估通過節點j的「最佳路徑」和通過節點k的「最佳路徑」的通信費用，立即找出哪一個節點在「最佳路徑」上。
這個實例說明在一個節點內可以只是根據從它的相鄰節點獲得的信息確定「最佳路徑」，這條路徑可以根據到達這個相鄰節點的鏈路的最新信息來加以選擇。一旦選擇了相鄰節點，消息被傳了出去，消息傳送問題就被同時交給了相鄰節點，相鄰節點必須利用從它的相鄰節點獲得的信息重複確定「最佳路徑」的操作。
路由選擇表最好在網絡中的每個節點都構造一個單獨的路由選擇表。但是，有時也需要每個節點產生第二個表。第二個表將包括備用路徑的信息。網絡中每個節點都在表中有一行。行的下標(或者行編號)可以是最終目標節點的地址。最終目標節點地址也可以是任意的，但是對於網絡中的每個節點而言它是獨一無二的，表的下標可以利用節點的地址來確定。任意行的欄目裡都包括最終目標地址和任意數量的下一節點地址，具體情況取決於要保存的備用路徑數量。對於每個下一節點，將一組完整的費用度量儲存在這個表中。收到新信息的時候，這種設計允許更新每一個度量，然後重新計算路徑費用，重新確定到達最終目標節點的最佳路徑。
在對應於特定表格中包括的節點的行中，節點根據它自己的狀況使用度量。例如，等待發射的消息的數量或者當前的處理器負擔估計。
路由選擇表實例中保存的變量在表1中說明。這個路由選擇表有一個參數Number_Paths，它是一個系統設計常量。這個Number_Paths表示要記住的到達目的地可能的不同路徑，最佳路徑和Number_Paths-1條路徑的數量。這樣的每條路徑都有一個唯一的First_Node。
消息的系統開銷發射一個數據包的時候，它一般都包括額外的系統開銷欄位來提供路徑方向信息和支持網絡學習。支持網絡學習的額外欄位的一個實例在表2中給出。這個欄位包括發射節點標識(XID)和支持學習功能的信息。節點要從它的路由選擇表中選擇幾條目標路徑，將它獲得的這些路徑的信息發射給它的相鄰節點來支持相鄰節點的學習。這樣，這些信息包括同樣的欄位組，每一組對應於一個目標節點。參數N說明消息中包括的組的數量。DID說明一組的目標節點。收到的時候，節點將這一組與對應於這一目的地的內部通信目錄中的行聯繫起來。適當的時候用收到的信息更新這一行。節點將獲得的這些路徑的信息發射給它的相鄰節點或者任意其它時候，它能夠在消息數據包中發射信息，或者可以是這個節點某種特殊廣播信道上的單獨一次廣播。
路由選擇信息分布本發明的一個重要特性是學習是在網絡發生變化的點進行的。然後學習過程從這個點擴展到周圍的點，並且按照這個方式進一步擴散。例如，如果這些節點剛好分布成一個六角形的形狀，那麼這一學習過程就擴展到包括另外的節點，特別象池子中滴入一滴水產生的波浪。這樣，隨著圓的半徑增大，新信息影響到的節點的數量按照圓的面積成正比地增長。結果，學習變化的節點的數量近似以正比於發射圓的數量的平方的速率改變。如上所述，學到的信息可以用一個消息數據包傳遞，也可以是這個節點上可用的某種特殊廣播通道上單獨的一次廣播。
認識到學習過程首先發生在發生變化的區域內也是非常重要的，在這個區域內的變化對路徑選擇的影響最大。只要需要，通過發生變化的這個區域的數據包會自動地重新定向，在數據包的始發節點第一次發射的時候，這種變化完全是不可預測的。
由於單獨一次變化導致的學習過程會導致幾個相鄰節點發生變化，因此下一層節點學習會起源於幾個節點調整它們的路徑選擇。因此，在單獨一次發射中，學習場能夠被用來將變化信息發射給一條以上的路徑是非常重要的。單獨一個消息數據包中發射三條路徑變化的信息，在多數情況下就能夠有效地更新學習，而不會導致不必要的系統開銷發射。
為了加速學習過程，數據包的學習部分填充在這之前沒有發生變化但是現在發生了變化的路徑的路徑信息是非常重要的。不管什麼時候路由選擇表中行的內容發生改變的時候，都要給它們作標記。構造一個數據包進行發射的時候首先選擇改變過的路由選擇表的行。與簡單地在路由選擇表的所有行中進行循環而不管它們是否發生了變化相比，將信息發射給整個網絡是一種更加有效的方法。這一技術強調的是信息的發射而不是數據的發射。
已經進行了仿真，操作員在計算機屏幕的一個區域內通過拖放符號創建空間上分布的節點陣。一旦放好，「點擊」一個符號，就能夠看到一個選項菜單，包括移動符號，查看仿真的前面板，或者顯示選中的節點中的各種存儲器陣列。每個節點都是節點對象單獨的一個實例，擁有它自己的存儲器陣列用於任務，擁有消息隊列和路由選擇表。因為每個節點都是一個對象的一個實例，所有節點都用相同的程序代碼來工作。利用這一仿真就能夠觀察無窮無盡的情景可能中的學習過程。
目前採用的鏈路模型嚴格地建立在距離的基礎之上。其它節點是在距離範圍內，通信完好，或者不在距離範圍內，根本不會進行通信。這就能夠簡化情景的設計，其中一些節點能夠互相直接通信，而另一些節點則不能。
一個實例情景是一個簡單十字叉。在這種情景中，這個區域裡放置了5個節點，如圖4所示。將這些節點叫做左節點、中心節點、右節點、上節點和下節點，以此來說明它們在圖中的相對位置。中心節點在所有其它節點的距離範圍之內。沒有任何其它節點能夠直接地互相通信。於是，它們之間的所有消息都要通過中心節點來傳遞。開始這一仿真，並且跟蹤學習進程。
仿真程序為每個節點隨機地選擇一個發射時間。這個事件驅動的仿真器採用單步方式，每次發射完以後在每個路由器中記錄學習過的路徑。結果列在表3中。仿真器時間列在第一欄內。第二欄說明已經發射了的節點。第三欄列出在發射的數據包中報告了它的路由選擇表項目的節點。剩下的欄說明作為發射結果的每個節點學習過的路徑。用一個三元組(x，y，z)來描述路徑，它們涉及到最終目的地x的路徑能夠通過下一節點是y，長度是z的一條路逕到達。長度指的是消息將通過的RF鏈路的數量。
在時刻0，每個節點都要了解它自己情況，因為還沒有進行任何通信。通過隨機選擇，節點4(上節點)成為第一個發射的節點，只能被節點2(中心節點)收到。中心節點了解到有一條路逕到達上節點，上節點是這條路徑上的下一節點，涉及到的鏈路數量是1(4，4，1)。
要發射的下一個節點是節點5(下節點)。學習結果的相似之處在於只有中心節點才能收到這一信號，並且了解到到下節點的一條路徑。下一步，碰巧是節點2(中心節點)發射。這個路由器有三個通信目錄行要發射，它們都代表到所有其它節點的新信息，它們都能收到這一消息。節點1(左節點)知道了到中心節點的一條直接路徑，以及通過中心節點到上節點和下節點的路徑。右節點得到了同樣的信息。上節點和下節點知道的路徑較少，因為它們對到達它們自己的路徑不感興趣。
在下面兩次發射過程中，中心節點了解到有兩條直接路逕到達右節點和左節點。輪到中心節點再次發射的時候，選擇修改過的路由選擇表行進行發射(1和3)，選擇到達4沒有修改過的路徑來填充三行學習欄位。剩餘的節點學習最後需要的信息，到此為止網絡就完整了。
圖5是為選中的參數說明確定最佳路徑的一個步驟實例的一個流程圖。一旦程序開始，就從本節點的觀察角度更新候選參數。例如，一個參數是候選路徑跳數，它等於候選跳數加1。候選對象是除了源節點和目標節點以外的路徑上可能的節點。參數的另一個實例是候選對象成功概率。候選路徑成功概率等於路徑中每條鏈路的候選對象成功概率乘以這條路徑中每條其它路徑的候選成功概率。更新完了候選參數以後，將候選參數與任意預先設置的門限進行比較。如果候選對象不符合這一門限值要求，就去掉這一候選對象。其它參數也是可以的，具體取決於網絡類型、節點類型、消息類型等這類事情。針對通過的那些候選對象，確定候選對象路徑費用。候選對象路徑費用是每條路徑每個參數的加權值。針對網絡確定加權值中每個參數的值，這個值會隨著時間變化，具體情況取決於通信類型和其它因素。這個值可以是這些參數的加權和，或者按照某個其它公式計算出來。將每個候選對象路徑費用與當前最佳路徑費用作比較，或者與其它候選對象的路徑費用作比較，如果這個節點上沒有以前的最佳路徑費用值。如果候選對象的路徑費用優於當前最佳路徑費用，就將當前路徑費用更換成候選對象的路徑費用，被替換的最佳路徑費用下降為次佳路徑費用，替換以前的值。同樣，如果候選對象的路徑費用優於當前次佳路徑費用，但是不比當前最佳路徑費用好，就將次佳路徑費用替換成候選對象的路徑費用。如果這個候選對象最佳路徑費用不比最佳或者次佳路徑費用好，那麼這個候選對象的路徑費用就被丟棄。顯然，本領域中的技術人員會明白，如果需要，每個節點都可以將最佳和次佳費用以外的其它費用保留下來。
例如在圖6中，節點D接收與一條或者多條路徑有關的相鄰節點E、F和G廣播的信息。節點D將收到的信息與節點D的路由選擇表中這些節點目前的最佳路徑信息進行比較，如果新收到的信息表明有一條路徑比路由選擇表中存在的最佳路徑或者次佳路徑更好，就更新節點D的表。節點D將更新後的數據廣播給它的相鄰節點。
權利要求
1.包括多個節點的一種網絡，所述節點中的每個節點都有存儲器、計算能力以及與一個或者多個其它節點通信的能力，其中從源節點發射給目標節點的信息是沿著有一個或者多個節點的一條路徑發射的，該路徑中接收所述信息的每個節點根據從每個相鄰節點收到的信息，為所述通信信息確定通過一個相鄰節點到達目標節點的最佳路徑。
2.權利要求1所述的網絡，其中相鄰節點產生關於路徑的新信息的時候，重新評估通信路徑。
3.權利要求2所述的網絡，其中的最佳路徑是使選中的費用函數最小的那一條。
4.權利要求3所述的網絡，其中的費用函數由用這個特定網絡目標定義的一個或者多個度量組成。
5.權利要求4所述的網絡，其中的度量包括到達目標節點以前，消息必須通過的節點的數量。
6.權利要求4所述的網絡，其中的度量包括通過一條路由成功通信的概率。
7.權利要求4所述的網絡，其中的度量包括在一段路由中成功發射的最小概率。
8.權利要求4所述的網絡，其中的度量包括網絡中單個節點的通信負擔。
9.權利要求4所述的網絡，其中的路徑是通過選擇一個參數，根據沿著這條路徑的單個最弱點，確定給定路由是不是這一發射的最佳路由來加以評估的。
10.權利要求4所述的網絡，其中的路徑是通過選擇一個參數，根據這條路徑上的單個最佳點，確定給定路由是不是這一通信的最佳路由來加以評估的。
11.權利要求4所述的網絡，其中一個值的確定針對的是選中的一組參數中的每一個參數，在每個參數相對值的基礎之上進行加權計算，以確定沿著這條路徑的最佳路由。
12.權利要求11所述的網絡，其中涉及到從一個節點傳遞消息的一條路徑的信息由所述節點只是從與所述節點直接通信的節點傳遞的信息來確定的。
13.權利要求9所述的網絡，其中涉及到從一個節點傳遞消息的一條路徑的信息由所述節點只是從與所述節點直接通信的節點傳遞的信息來確定的。
14.權利要求1所述的網絡，其中到目標節點的節點鏈上第一個節點的選擇取決於每個節點利用從相鄰節點收到的信息計算這個網絡中到每個其它節點的最佳路徑時產生的數據。
15.權利要求2所述的網絡，其中用於路徑選擇的信息保存在每個節點的一個表中。
16.權利要求15所述的網絡，其中的每個表都有按照最終目的地排列的一行或者多行，以及每個都包括這個節點為到達這個目的地的路徑計算的具體度量的一列或者多列。
17.權利要求16所述的網絡，其中放進節點的表裡的信息是通過處理從每個相鄰節點的表獲得的信息來確定的。
18.權利要求4所述的網絡，其中的度量可以用單獨的一次發射發射給相鄰節點。
19.權利要求4所述的網絡，其中的度量可以串聯正常的消息一起發射給相鄰節點。
20.權利要求18所述的網絡，其中根據最後一次的更新時間來確定度量變化的優先級。
21.在有多個節點的網絡內從源節點向目標節點發射信息的一種方法，包括根據從每個相鄰節點收到的信息，為源節點到目標節點通過每個相鄰節點的信息傳送確定最佳路徑；沿著被確定為向所述目標節點傳遞所述信息的最佳路徑，從所述源節點發射所述信息給相鄰接收節點；根據從每個相鄰節點收到的信息，確定從接收節點通過每個相鄰節點到達目標節點的最佳路徑；繼續這些步驟，直到目標節點收到這些信息。
22.權利要求21所述的方法，其中相鄰節點產生關於路徑的新信息的時候，重新評估通信路徑。
23.權利要求22所述的方法，其中的最佳路徑是使選中的費用函數最小的那一條。
24.權利要求23所述的方法，其中的費用函數由用這個特定網絡目標定義的一個或者多個度量組成。
25.權利要求24所述的方法，其中的度量包括到達目標節點以前，消息必須通過的節點的數量。
26.權利要求24所述的方法，其中的度量包括通過一條路由成功通信的概率。
27.權利要求24所述的方法，其中的度量包括在一段路由中成功發射的最小概率。
28.權利要求24所述的方法，其中的度量包括網絡中單個節點的通信負擔。
29.權利要求24所述的方法，其中的路徑是通過選擇一個參數，根據沿著這條路徑的單個最弱點，確定給定路由是不是這一發射的最佳路由來加以評估的。
30.權利要求24所述的方法，其中的路徑是通過選擇一個參數，根據這條路徑上的單個最佳點，確定給定路由是不是這一通信的最佳路由來加以評估的。
31.權利要求24所述的方法，其中一個值的確定針對的是選中的一組參數中的每一個參數，在每個參數相對值的基礎之上進行加權計算，以確定沿著這條路徑的最佳路由。
32.權利要求31所述的方法，其中涉及到從一個節點傳遞消息的一條路徑的信息由所述節點只是從與所述節點直接通信的節點傳遞的信息來確定的。
33.權利要求29所述的方法，其中涉及到從一個節點傳遞消息的一條路徑的信息由所述節點只是從與所述節點直接通信的節點傳遞的信息來確定的。
34.權利要求22所述的方法，其中用於路徑選擇的信息保存在每個節點的一個表中。
35.權利要求34所述的方法，其中的每個表都有按照最終目的地排列的一行或者多行，以及每個都包括這個節點為到達這個目的地的路徑計算的具體度量的一列或者多列。
36.權利要求24所述的方法，其中的度量可以用單獨的一次發射發射給相鄰節點。
37.權利要求24所述的方法，其中的度量可以與正常的消息並置發射給相鄰節點。
38.權利要求24所述的方法，其中發射給相鄰節點的度量變化根據它們最後一次更新的時間被確定優先級。
39.權利要求37所述的方法，其中通過網絡發射路徑度量信息只是將相對少量的系統開銷增加到正常發射的消息中去。
40.包括多個節點的網絡中的一種節點，該節點有存儲器、計算能力以及與一個或者多個其它節點通信的能力，該節點用於接收從源節點發射給目標節點的信息，該節點用於沿著包括一個或者多個節點的一條路徑發射所述信息，這個節點根據從所述相鄰節點收到的信息確定通過相鄰節點到目標節點的最佳路徑。
全文摘要
本發明涉及用通信鏈路互相連接的一種網絡節點。每個節點都能夠確定從它自己到可能的許多其它節點的通信路徑或者路由，或者是直接的或者是通過其它節點，從而使這個網絡變得完整。產生關於一條路由的新信息的時候根據選好的判據評估這些路徑，找出、記住並且在通信的時候使用最佳路徑。本發明涉及到確定通過網絡的最佳路徑，並且在通信狀況和節點數量發生變化的時候維護好這些路徑。
文檔編號H04L12/56GK1518818SQ02809962
公開日2004年8月4日 申請日期2002年3月11日 優先權日2001年3月14日
發明者D·查菲, G·馬修斯, L·德阿加蒂, ⒓擁, D 查菲, 匏 申請人:無線電話公司