使用樹狀拓撲建立最佳路由的設備和方法

2023-05-04 17:23:06

專利名稱：：使用樹狀拓撲建立最佳路由的設備和方法
技術領域：
：本發明一般涉及無線個人區域網(WPAN)，更具體地涉及基於樹狀拓撲(treetopology)在WPAN內建立從源節點到目的節點的路由的設備和方法。
背景技術：
：通常，在移動通信系統中，在移動單元與基站之間發送和接收數據。即，移動單元和基站直接發送和接收數據，無需經過其他節點。與此相反，開發了無線個人區域網(WPAN)，用於在較短範圍內互連裝置。WPAN是能使多個節點相互通信的特定(ad-hoc)數據通信系統。包含在該特定網絡內的發送節點經其他節點將數據發送到接收節點。如果接收節點與發送節點相鄰，就能夠在這些節點之間直接傳送數據。現在參考圖1，描述一種根據傳統路由算法的數據傳輸，該路由算法與基於樹狀拓撲構成該特定網絡的節點相關。圖1的特定網絡至少包括兩個節點。這些節點被分為兩類。一類是維護路由選擇表(routingtable)並被稱為「N+」的節點。另一類是沒有路由選擇表並被稱為「N-」的節點。下面描述在包括N+和N-的特定網絡內建立路由的傳統方法。假設節點A是源節點，並且節點I是目的節點。源節點請求建立到目的節點的路由。因此，其是N+的節點A檢測其路由選擇表是否包含與目的節點I相關的路由信息。如果不包含，則節點A在步驟S100將路由請求RREQ消息廣播給相鄰節點，以建立到節點I的路由。其是N+的節點B在其路由選擇表內查找關於接收到的RREQ消息的目的節點I的路由信息。如果存儲了該路由信息，則節點B利用路由應答RREP消息進行應答。如果沒有存儲該路由信息，則在步驟S102和S108將路由信息欄位創建到其路由選擇表內，並對相鄰節點廣播RREQ消息。其是N+的節點C在步驟S104和S106也執行與節點B相同的操作。當從節點B接收到RREQ消息時，其是N-的節點G在步驟S128發送RREP消息給節點B，以應答RREQ消息。根據傳統算法，該特定網絡內的N-發送RREP消息來應答RREQ消息。雖然該N-自身不是接收到的RREQ消息所請求的目的節點，但是它根據樹狀拓撲及其節點特性來發送RREP消息。即，由於N-不具有它自己的路由選擇表，甚至在接收到RREQ消息後，N-也不能存儲或查找路由信息，而且由於樹狀拓撲僅允許消息傳輸到上遊節點或下遊節點，進一步的路由搜索是不可行的。在步驟S120中，來自節點G的RREP消息經節點B被轉發到節點A。通常，在樹狀拓撲的創建階段，每個節點在其相鄰列表內存儲關於例如1跳躍(hop)等某距離內的節點的信息。其是N-的節點D執行與節點G相同的操作。因此，由節點D產生的RREP消息在步驟S124、S122和S120經節點C和B被轉發到節點A。當接收到來自節點C的RREQ消息時，其是N+的節點F在步驟S110、S112和S114能夠廣播RREQ消息。節點E執行與節點G相同的操作。節點H在步驟S116將接收到的RREQ消息轉發給節點I。當接收到RREQ消息時，節點I認識到節點A為其請求路由的節點是它自己。因此，節點I產生RREP消息來應答RREQ消息。該RREP消息沿RREQ消息的路由被轉發到節點A。結果，在節點A和節點I之間建立了路由。雖然沒有描述，具有路由選擇表的N+通過使用接收的RREQ消息信息將關於目的節點的欄位創建到其路由選擇表內，並將接收的RREQ消息發送到相鄰節點。通常，N+更新並轉發跳躍總數(hopcount)到相鄰節點。選擇具有最小跳躍總數的路由作為節點之間的路由。然後，N+接收用於應答RREQ消息的RREP消息，並通過填充為相關節點創建的路由選擇表的欄位值來管理它們的路由選擇表。根據前述內容，節點A接收用於應答單個RREQ消息的多個RREP消息。同時，來自N-的RREP消息不是必要的。圖2顯示基於傳統算法的使用節點在特定網絡內建立路由的另一個示範過程，在此過程中，可建立從源節點到目的節點的前向路由(forwardroute)，該路由不同於從目的節點到源節點的反向路由(backwardroute)。節點A請求建立到節點E的路由。節點A通過查找所存儲的路由選擇表來確定是否已建立到節點E的路由。如果確定沒有到節點E的路由，則節點A在步驟S200廣播RREQ消息。當接收到RREQ消息時，節點B也查找所存儲的路由選擇表，並確定是否建立了到節點E的路由。如果確定沒有到節點E的路由，則節點B在步驟S202廣播該RREQ消息。節點C確定它自己是否是節點A請求為其建立路由的節點。由於節點C不是節點A請求為其建立路由的節點，其是N-的節點C在步驟S204沿樹狀路由發送RREQ消息到節點D。節點D也確定它自己是否是節點A請求為其建立路由的節點。由於節點D不是節點A請求為其建立路由的節點，節點D在步驟S206發送RREQ消息給節點E。節點E認識到它自己就是節點A請求為其建立路由的節點。節點E產生RREP消息以應答RREQ消息。所產生的RREP消息在步驟S210被發送給節點D。節點D在步驟S212將接收的RREP消息發送給節點F。節點F沿樹狀路由將RREP消息轉發給源節點A。結果，前向路由不同於反向路由，因此需要一種解決此問題的方案。
發明內容為解決相關技術的上述缺點，本發明的一個方面是提供一種能夠在無線網絡中建立最佳路由的設備和方法，該無線網絡包含樹狀拓撲結構和具有有限功能的節點(例如，由於缺少其自己的路由選擇表而不具有按需(on-demand)路由選擇建立功能的N-)。本發明的另一個方面是提供一種能夠防止接收用於應答RREQ消息的多個RREP消息的設備和方法。本發明的另一個方面是提供一種能夠建立與前向路由相同的反向路由的設備和方法。本發明的另一個方面是提供一種用於以最小鏈路成本，通常以具有最小跳躍總數，來建立到目的節點的最佳路由的設備和方法。為實現本發明的以上方面，提供一種具有樹狀拓撲的移動通信系統中通過中間節點來中繼(relay)路由請求RREQ消息的方法，該中間節點與至少一個節點連接，該移動通信系統包含目的節點和源節點，該源節點經至少一個中間節點來發送RREQ消息到目的節點，上述方法包含根據目的節點的位置來確定是使用路由選擇路由(routesroute)還是使用按需系統的表驅動方案(table-drivenscheme)來搜索並建立路由，當沿著除樹狀路由之外的路由接收到RREQ消息時，使用它所存儲的信息來更新用於搜索反向路由的第一信息，並發送包含更新的第一信息的RREQ消息。此外，提供一種在具有樹狀拓撲的移動通信系統中建立從源節點到目的節點的路由的設備，該移動通信系統包含目的節點和源節點，該源節點經至少一個中間節點發送RREQ消息給目的節點，上述設備包含源節點，用於根據目的節點的位置來確定使用預先建立的樹狀路由或者按照需要通過廣播RREQ消息來搜索新路由的路由建立方法，根據該確定來創建路由請求RREQ消息，並且發送所創建的RREQ消息；至少一個中間節點，用於傳送RREQ消息，當沿著除樹狀路由之外的路由接收到RREQ消息時，使用它的信息來更新該RREQ消息的第一信息；以及目的節點。從下面結合附圖對實施例的說明，本發明的這些和/或其他的方面和優點將變得更清楚，並且更容易被理解，其中圖1是表示基於樹狀拓撲的特定網絡中的傳統路由選擇的一個例子的示意圖；圖2是表示基於樹狀拓撲的特定網絡中的傳統路由選擇的另一個例子的示意圖；圖3是表示根據本發明一個實施例的樹狀路由選擇的示意圖；圖4是表示根據本發明一個實施例的RREQ接收節點的示範步驟的流程圖；圖5是表示根據本發明一個實施例的RREP接收節點的示範步驟的流程圖；圖6是表示根據本發明一個實施例的數據接收節點的示範步驟的流程圖；圖7是表示根據本發明一個實施例的缺點的示意圖；圖8是表示根據本發明一個實施例的另一個缺點的示意圖；圖9是表示根據本發明另一個實施例的路由建立的示意圖；圖10是表示根據本發明另一個實施例的RREQ接收節點的示範步驟的流程圖；和圖11是表示根據本發明另一個實施例的RREP接收節點的示範步驟的流程圖。具體實施例方式現在將詳細參照本發明實施例，它們的例子顯示在附圖中，其中相同的參考標記始終表示相同的元件。為了解釋本發明，以下參考實施例。在進行詳細的說明之前，先說明術語的定義。樹狀路由指在根據按需方案(on-demandscheme)使用RREQ和RREP消息建立路由之前在節點之間預先建立的路由。路由是使用在源節點和目的節點之間進行通信的中間節點建立的。後代節點(descendentnode)是從相關節點沿樹狀結構進一步向下的節點，即，具有更大深度的節點。祖先節點(ancestornode)是從其相關後代節點沿樹狀結構向上的節點，即，具有較小深度的節點。父節點(parentnode)是相關節點的祖先節點，它沿樹狀結構向上跟隨。子節點(childnode)是相關節點的後代節點，它沿樹狀結構向下跟隨。根據本發明的實施例，源節點根據其類型(N+或N-)和目的節點的位置來確定路由選擇方法。如果目的節點是在與源節點即後代節點相同的簇內的祖先節點或者目的節點的簇具有比源節點的簇更大的深度，則最佳路由使用預先建立的樹狀路由來發送數據分組。否則，與使用路由選擇路由(routeroutes)相比較，最佳路由通過廣播RREQ消息來使用按需方案。在下文中，說明當將在源節點的應用程式內創建的數據發送到目的節點時的路由選擇方法。返回來參考圖1，如果節點F是源節點，並且節點A是目的節點，節點F的後代節點是節點E、H和I，而節點F的祖先節點是節點C、B和A。通過分析目的節點A的地址，源節點F可以定位(spot)目的節點和源節點在樹狀結構內的相對位置。也就是說，源節點F定位目的節點A是它的祖先節點。通過樹狀路由器計算，認識到節點A是沿樹狀路由的祖先節點，節點F發送數據分組給節點A。節點F能將關於節點A是沿樹狀路由的祖先節點的信息存儲到它的路由選擇表中。如果該信息被存儲到路由選擇表中，則節點F使用路由選擇表內的信息來發送數據分組到節點A，而不進行樹狀路由器計算。因此，節點F通過樹狀路由器計算來定位節點A位置，花費更少的時間。可選地，節點F可將某種信息附加到被發送的數據。上述某種信息指示當附加到數據中的目的節點的地址與數據接收節點的地址不同時，沿樹狀路由將數據中繼到父節點。因此，節點C將數據中繼到節點B，而不使用節點A的地址進行位置定位。節點B也將接收的數據中繼到節點A。因為源節點僅通過分析目的節點的地址並定位目的節點的相對位置而不必建立路由，來發送數據到其是樹狀結構中的祖先節點的目的節點，因此減少了路由建立時間。結果，減少了數據傳輸的總時間。源節點能夠僅通過一次樹狀路由器計算來發送數據分組到目的節點。-本發明的第一實施例根據本發明的第一實施例，源節點建立到目的節點的路由。首先，說明N-沿樹狀路由的情形，隨後說明N+沿樹狀路由的另一種情形。1.樹狀結構中的N-如果N-是源節點，則N-源節點確定目的節點是否是它的沿樹狀路由的後代節點或祖先節點。雖然沒有存儲路由選擇表，N-可以通過分析目的節點的地址來確定目的節點是否是它的後代節點或祖先節點，以便根據該確定使用所連接的樹狀路由來發送數據分組。N-源節點使用位於到目的節點的路由上的N+作為其代理節點(agentnode)，來搜索路由。如果N-是中間節點，則N-中間節點通過分析目的節點的地址，將所接收到的數據中繼到其沿樹狀路由的父節點或子節點。當接收到RREQ消息時，N-根據接收到的RREQ消息的傳輸類型(廣播或單播)進行操作。即，當接收到廣播RREQ消息時，N-定位發送RREQ消息的節點的相對位置，並僅當該RREQ消息是從其子節點接收的並且該RREQ消息的最終目的節點是它的後代節點時，使用其樹狀路由來發送(單播)接收的RREQ消息。因此，不必要的RREQ消息就不會被發送和接收。當接收到單播RREQ消息時，取決於目的節點的相對位置，N-中間節點沿適當的樹狀路由來發送(單播)接收到的RREQ消息。下面說明一種N-確定接收到的RREQ消息是廣播消息還是單播消息的方法。一般地，發送RREQ消息的節點確定是否廣播或單播該RREQ消息。如果確定為單播，則節點將要接收RREQ消息的節點地址添加到RREQ消息的目的地址欄位中，然後發送RREQ消息。當確定為廣播時，節點將在系統設計早期階段所設置的廣播地址信息添加到RREQ消息目的地址欄位內，然後發送RREQ消息。當接收到RREQ消息時，接收節點自己能夠通過比較目的地址欄位和它自己的地址信息，知道該RREQ消息是被廣播還是被單播到它自己的。說明當N-是目的節點的情況。當接收到由樹狀結構內位於RREQ消息的源節點與目的節點之間的後代節點所廣播的RREQ消息時，N-創建RREP消息，並使用包含在接收的RREQ消息內的路由信息來發送RREP消息。當接收到單播RREQ消息時，N-創建並發送RREP消息。2.樹狀結構中的N+如果某個N+節點的應用程式內創建的數據將要被發送到某個目的節點，或者當從相鄰節點接收到數據分組時N+成為源節點，則具有它自己的路由選擇表的N+在該路由選擇表內查找目標信息。如果有，則N+發送數據分組到存儲在路由選擇表中的下一個跳躍地址。如果沒有，則源節點通過分析目的節點的地址信息來定位目的節點的相對位置。如果目的節點是源節點的相鄰節點或後代節點，則源節點沿相關樹狀路由發送數據分組。否則，源節點通過RREQ消息廣播來搜索路由，從而建立新路由。接收的數據分組的傳輸可被阻止，直到結束搜索為止。根據搜索結果，源節點在接收的RREP消息中選擇具有最小鏈路成本(通常，為跳躍總數)的RREP消息，在路由選擇表中存儲相關信息，並沿相關路由發送數據分組。當N+是中間節點並接收數據分組時，N+執行與源節點相同的操作。如果接收到RREQ消息，則N+在路由選擇表中查找相關信息。如果存儲了該相關信息，則N+回復RREP消息，並且如果沒有存儲相關信息，則N+分析地址。如果目的節點是它的後代節點，則N+使用相關樹狀路由來將接收到的數據發送到目的節點。如果目的節點不是它的後代節點，則N+向相鄰節點廣播接收到的RREQ消息。如果N+是目的節點，則N+在其路由選擇表中查找，並確定是否從相關源節點接收了RREQ消息。如果最初接收了RREQ消息，則N+將關於相關源節點的信息記錄到路由選擇表中，並回復RREP消息。如果接收到重疊的RREQ消息，則N+比較預先存儲的鏈路成本值與接收的RREQ消息的鏈路成本值。當接收的RREQ消息具有較小值時，N+更新路由選擇表信息，並回復RREP消息。現在參考圖3，主要參考一個確定的實施例來說明本發明。源節點是節點E，並且目的節點是節點I。其是沒有路由選擇表的N-的源節點E在步驟S300沿樹狀路由發送數據到父節點B。其是樹狀結構中的終端節點的源節點E具有到其父節點的一條樹支。因此，源節點E使用父節點B作為代理節點來發送數據分組，而不分析目標地址。其是N+的節點B從接收的數據中提取目的節點的地址信息，並在其路由選擇表中查找關於目的節點的路由信息。如果沒有存儲該信息，則節點B使用所提取的地址信息來分析目的節點的位置。由於圖3的目的節點I不是節點B的後代節點，節點B在步驟S302、S304和S306存儲接收的數據，並創建和廣播RREQ消息。節點F丟棄接收的RREQ消息，因為接收的RREQ消息是來自沿樹狀路由的祖先節點的廣播消息。N+節點C在步驟S308、S310、S312和S314使用接收的RREQ消息內的信息，來更新它的路由選擇表的目的信息，並廣播接收的RREQ消息。節點G和H丟棄接收的RREQ消息。如果節點A維護關於目的節點I的路由選擇表，則從節點B和C兩者接收RREQ消息的節點A就能夠獲得目的節點I的位置。節點A發送RREP消息，以應答接收的RREQ消息。此時，節點A比較接收的RREQ消息的跳躍總數，並僅為具有最小跳躍總數的RREQ消息發送RREP消息。還參考圖3，節點A僅發送RREP消息到節點B。如果沒有維護關於目的節點I的路由選擇表，則節點A單播RREQ消息到節點D，因為節點A知道該目的節點不是它的後代節點。為簡明起見，省略了對於從節點A發送的RREQ消息的詳細說明。在步驟S316，節點D單播更新的RREQ消息到目的節點I。目的節點I在步驟S318創建RREP消息以應答RREQ消息，並單播所創建的RREQ消息到節點D。當接收到RREQ消息時，節點D在步驟S320使用存儲在路由選擇表中的信息來發送更新的RREP消息到節點C，並且節點C在步驟S322以相同方式來發送更新的RREP信息到節點B。結果，建立了從節點B到目的節點I的用於傳送數據的路由。沿著所建立的路由，節點B發送存儲的數據到目的節點I。圖4顯示根據本發明一個實施例的RREQ接收節點的示範步驟。節點在步驟S400接收RREQ消息。該節點在步驟S402使用接收的消息來確定它自己是否是目的節點。如果該節點是目的節點，則該節點在步驟S416確定它自己是否是N+。如果該節點不是目的節點，則該節點在步驟S404確定它自己是否是N+。如果該節點是N+，則該節點在步驟S406確定RREQ消息的目的節點是否是它的後代節點。如果目的節點不是後代節點，則該節點在步驟410更新並轉播接收的RREQ消息。如果目的節點是後代節點，則該節點在步驟408更新並單播接收的RREQ消息。同時，如果節點不是N+，則該節點在步驟S412確定接收的RREQ消息是否是從後代節點單播或廣播的。如果是，則該節點在步驟408更新並單播接收的RREQ消息。如果不是，則該節點在步驟S414丟棄接收的RREQ消息。如果在步驟S416中節點是N+，則該節點在步驟S418比較接收的RREQ消息的鏈路成本與存儲在路由選擇表中的鏈路成本。如果接收的RREQ消息具有較小的鏈路成本，則節點在步驟S420更新路由選擇表中的關於接收RREQ消息的信息。如果接收的RREQ消息的鏈路成本並不小，則該節點在步驟S414丟棄接收的RREQ消息。該節點在步驟S422創建RREP消息以應答接收的RREQ消息。圖5是表示根據本發明一個實施例的RREP接收節點的示範步驟的流程圖。節點在步驟S500接收RREP消息。節點在步驟S502確定它自己是否是源節點。如果是，則該節點在步驟S504確定它自己是否是N+。如果該節點不是N+，則N+在步驟S506丟棄RREP消息。如果該節點是N+，則在步驟S508確定接收的RREP消息是否是新RREP消息。如果是，則該節點在步驟S514創建新的關於相關源節點的路由選擇表信息，並更新路由選擇表。如果不是，即如果該RREP消息已經被接收，則該節點在步驟S512比較RREP消息的鏈路成本與路由選擇表中的鏈路成本。如果接收的RREP消息的鏈路成本小於存儲的鏈路成本，則節點在步驟S514用相關信息更新路由選擇表，並在步驟S506丟棄RREP消息。如果在步驟S502中該節點不是源節點，則該節點在步驟S518確定它自己是否是N+。如果該節點是N-，則該節點在步驟S520單播RREP消息。如果該節點是N+，則該節點在步驟S522確定接收的RREP消息是否是新RREP消息。如果是，則該節點在步驟S524創建關於相關節點的路由選擇表信息，並更新路由選擇表，並且在步驟S526發送該RREP消息。如果不是，即如果該節點在路由選擇表內維護有相關信息，則在步驟S528，該節點比較RREP消息的鏈路成本與相關信息的鏈路成本。如果RREP消息具有較小鏈路成本，則該節點在步驟S524更新關於相關源節點的路由選擇表信息，並在步驟S526發送RREP消息。如果RREQ消息不具有較小鏈路成本，則該節點在步驟S506丟棄RREP消息。圖6是表示根據本發明一個實施例的數據接收節點的示範步驟的流程圖。步驟S600是當節點從應用程式(較高層)接收數據的情況，而步驟S602是當節點從相鄰節點(較低層)接收數據的情況。如果節點在步驟S602接收數據，則該節點在步驟S614確定它自己是否是目的節點。如果是，則該節點在步驟S616發送數據到較高層。如果不是，則該節點在步驟S604確定它自己是否是N+。如果是，則該節點在步驟S606確定它的路由選擇表是否存儲了目的信息。如果存儲了目的信息，則該節點在步驟S608發送數據到下一跳躍節點，並在步驟S610啟動計時器。如果沒有存儲目的信息，則該節點在步驟S618定位目的節點的相對位置。如果目的節點是它的後代節點或者能夠被定位的相鄰節點，則該節點在步驟S612沿相關樹狀路由發送數據。如果不是，則該節點在步驟S620創建並廣播RREQ消息，以搜索路由。如果在步驟S604中節點是N-，則該節點在步驟S612沿樹狀路由發送數據。下面參考圖7和8顯示一個實施例的缺點(drawback)。圖7顯示當根據本發明第一實施例執行路由選擇時未能建立最佳路由的情形。假設節點A是源節點，並且節點I是目的節點。源節點A在步驟S700發送數據到節點B，並且節點B在步驟S702將數據中繼到節點C。節點C在步驟S704和S706將接收的數據存儲到緩衝器，並創建和廣播RREQ消息。為簡明起見，省略了對步驟S704的詳細說明。節點F在步驟S708更新並廣播接收的RREP消息。節點G在步驟S710通過分析RREQ消息內包含的關於目的節點的信息，來更新並單播接收的RREQ消息到目的節點I。目的節點I沿著RREQ消息的反向路由來轉發RREP消息。結果，沿節點A→B→C→F→G→I建立路由。該路由不是最佳的，因為最佳路由是沿節點A-H-I的路由。圖8顯示根據本發明第一實施例的建立不同於前向路由的返向路由的情形。前向路由選擇表示從源節點到目的節點的路由，而返向路由選擇表示從目的節點到源節點的路由。參考圖8，源節點是節點A，並且目的節點是節點M。源節點A在步驟S800廣播RREQ消息以建立到目的節點M的路由。節點I在步驟S802和S804更新接收的RREQ消息，並廣播更新的RREQ消息。節點K接收並更新廣播的RREQ消息。節點K在步驟S810和S816廣播更新的RREQ消息，並且目的節點M接收RREQ消息。為簡明起見省略了對步驟S806、S808、S812和S814的詳細說明。最後，沿節點A→I→K→M建立了前向路由。當接收到RREQ消息時，其是N-的目的節點M在步驟S818單播RREP消息到節點L。N-節點L在步驟S820更新並單播接收的RREP消息到節點G。N-節點G在步驟S822更新並單播接收的RREP消息到節點F。在步驟S824、S826、S828、S830和S832，RREP消息最終被發送到節點A。因此，沿節點M→L→G→F→E→D→C→B→A建立反向路由。正如所示，根據本發明的第一實施例，前向路由和反向路由相互不同。根據本發明的第二實施例，能夠解決此缺點，下面詳細地說明本發明的第二-本發明第二實施例根據本發明的第二實施例，能包含確定信息的路由選擇表被分配給N-節點，並提出邊界節點(bordernode)的概念。1.樹狀結構中的N-如果N-節點是源節點，則N-節點將要發送的數據存儲到緩衝器中，並定位目的節點的位置。當目的節點是它的後代節點時，N-節點沿樹狀路由發送數據，不必搜索路由。如果目的節點不是它的後代節點，甚至N-節點也創建用於相關目的節點的路由選擇表，並廣播RREQ消息。如果N-節點是中間節點，並接收到單播的RREQ消息，則N-節點沿樹狀路由更新並發送接收的RREQ消息。如果RREQ消息的源節點是它的後代節點，並且N-節點從其子節點接收到廣播的RREQ消息，則N-節點更新並沿樹狀路由發送接收的RREQ消息。如果N-節點是目的節點，則N-節點創建RREP消息以應答接收的RREQ消息，存儲包含在RREQ消息內的下一個邊界節點的信息，並發送創建的RREP消息。甚至N-也為相關源節點創建並維護路由選擇表。2.樹狀結構中的N+N+執行與在本發明第一實施例中所述過程的相同的過程。圖9顯示根據本發明第二實施例的前向路由與反向路相同的情形，下面將對此進行詳細說明。在圖9中，源節點是節點A，並且目的節點是節點L。源節點A通過分析目的節點的地址得知目的節點不是它的後代節點。源節點A執行路由搜索以建立路由，並因為不發送數據給節點B而有別於第一實施例。更具體地，源節點A在步驟S900和S902創建RREQ消息並廣播創建的RREQ消息。為簡明起見，省略對於從源節點A發送到節點B的RREQ消息的詳細說明。節點K在步驟S904更新並廣播接收的RREQ消息。因為節點K不是沿樹狀路由接收到RREQ消息的，節點K將表示它自身能夠是邊界節點的信息附加到RREQ消息中。邊界節點指的是沿著除樹狀路由之外的路由接收RREQ消息並且只沿樹狀路由發送更新的RREQ消息的節點。節點J從節點K接收廣播的RREQ消息，並認識到節點K是邊界節點。由於節點J沿樹狀路由接收RREQ消息，節點J使用接收的RREQ消息認識到節點K是邊界節點。節點J將指示節點K是邊界節點的信息附加到RREQ消息中。節點J還存儲節點K是邊界節點。節點J在步驟S906單播更新的RREQ消息到節點I。如在本發明第一實施例中提到的，當從其子節點接收到RREQ消息時，N-中間節點更新並單播接收的RREQ消息。節點I在步驟S908和S910更新並廣播接收的RREQ消息。節點N在步驟S914廣播接收的RREQ消息。此時，節點N將它自身能夠是邊界節點候選者(bordernodecandidate)附加到RREQ消息中。當從節點N接收到廣播的RREQ消息時，節點O認識到節點N是邊界節點。因此，節點O更新包含在接收的RREQ消息內的關於邊界節點的信息。節點O將節點N是邊界節點存儲到其路由選擇表中。在更新了接收的RREQ消息後，節點O在步驟S918單播更新的RREQ消息到節點M。節點M在步驟S920更新並單播接收的RREQ消息到節點L。節點H在步驟S912更新並廣播接收的RREQ消息。在從節點H接收到廣播的RREQ消息後，節點P在步驟S916單播接收的RREQ消息到節點O。節點O在步驟S918更新並單播接收的RREQ消息到節點M。節點M在步驟S920更新並並單播接收的RREQ消息到節點L。因此，節點L可以接收多於兩個的RREQ消息，並選擇兩個RREQ消息中具有最小鏈路成本的RREQ消息。結果，沿節點A→K→J→I→N→O→M→L建立前向路由。雖然未在此描述，每個N+將包含在RREQ消息內的信息存儲到它的路由選擇表中。在下文中，說明反向路由選擇。節點L存儲包含在接收的RREQ消息內的關於下一個邊界節點的信息，並在步驟S922將所創建的包含相關信息的RREP消息發送給節點M。節點M在步驟S914更新並轉發接收的RREP消息。節點O在步驟S926使用包含在RREP消息內的邊界節點信息將RREP消息轉發到節點N。節點N用它所存儲的邊界節點(節點K)信息，來更新接收的RREP消息內關於下一個邊界節點的信息，並在步驟S928轉發接收的RREP消息到節點I。最後，在步驟S930、S932和S934將RREP消息轉發到節點A。結果，建立了與前向路由相同的反向路由。圖10是顯示根據本發明另一實施例的RREQ接收節點的示範步驟的流程圖。在步驟S1000，節點接收RREQ消息。該節點在步驟S1002確定所接收的RREQ消息是否包含邊界節點候選者的信息並且是從其子節點發送來的。如果是，則該節點在步驟S1004將邊界節點候選者作為邊界節點存儲到它的路由選擇表中。在步驟S1006，該節點更新接收到的RREQ消息中的邊界節點信息。如果RREP消息不包含邊界節點信息，並且不是從子節點傳送來的，則該節點在步驟S1008將包含在RREQ消息內的邊界節點信息存儲到它的路由選擇表中。該節點在步驟S1010確定它自己是否是N+。如果是N+，則該節點在步驟S1012確定所接收的RREQ消息是否是廣播的。如果是，則該節點在步驟S1016用它自己的信息，來更新包含在RREQ消息內的邊界節點候選者信息。然後，該節點在步驟S1020確定目的節點是否是它的後代節點。如果是，則該節點在步驟S1024沿樹狀路由單播更新的RREQ消息。如果不是，則該節點在步驟S1026刪除所存儲的RREQ邊界節點候選者信息，並廣播更新的RREQ消息。如果在步驟S1010中該節點是N-，則在步驟S1014該節點確定所接收的RREQ消息是否是廣播的。如果是，則該節點在步驟S1018確定目的節點是否是它的後代節點。如果是，則該節點在步驟S1024沿樹狀路由單播更新的RREQ消息。如果不是，則該節點在步驟S1022丟棄接收的RREQ消息。圖11是表示根據本發明另一實施例的RREP接收節點的示範步驟的流程圖，下面將對此進行詳細說明。節點在步驟S1100接收RREP消息。在步驟S1102，節點確定它自己是否是N+。如果不是，則該節點在步驟S1106用樹狀路由以及它的路由選擇表，將接收到的RREP消息轉發到邊界節點。如果是，則該節點在步驟S1104確定路由選擇表是否維護源節點信息。如果沒有維護，則該節點在步驟S1114沿樹狀路由轉發RREP消息。如果該節點維護了源節點信息，則在步驟S1108該節點確定它自己是否是邊界節點。如果不是，則該節點在步驟S1110更新包含在RREP消息內的邊界節點信息。即，節點使用由該節點維護的邊界節點信息來更新RREP消息。如果是，則該節點使用它的路由選擇表來更新所接收的RREP消息，並在步驟S1112轉發更新的RREP消息。根據以上說明，由於N-存儲最少量的信息，並且所存儲的信息被用於路由選擇，因此能夠建立與前向路由相同的反向路由。此外，能夠建立最佳或近似最佳路由。雖然已經說明了本發明的實施例，當本領域技術人員了解了本發明的基本發明概念時，他們可以想到實施例的其他變化和修改。因此，期望所附權利要求被解釋為不僅包括以上實施例，還包括這種落入本發明實質和範圍內的所有變化和修改。權利要求1.一種具有樹狀拓撲的無線通信系統中通過中間節點來中繼路由請求RREQ消息的方法，所述中間節點沿樹狀路由與至少一個節點連接，所述移動通信系統包括目的節點和源節點，所述源節點經由至少一個中間節點將所述RREQ消息發送到所述目的節點，所述方法包括當沿著除所述樹狀路由之外的路由接收到所述RREQ消息時，使用所存儲的信息來更新用於搜索反向路由的第一信息；以及發送包含被更新的第一信息的RREQ消息。2.根據權利要求1的方法，其中，僅當從後代節點接收到沿著除所述樹狀路由之外的路由接收到的所述RREQ消息時，更新並發送所接收的RREQ消息。3.根據權利要求1的方法，進一步包括當沿著所述樹狀路由接收到包含所述第一信息的RREQ消息時，使用所存儲的信息來更新用於搜索所述反向路由的第二信息。4.根據權利要求3的方法，其中，被更新的第二信息被存儲到路由選擇表中。5.根據權利要求3的方法，其中，當所述RREQ消息中包含的目的節點是所述後代節點時，單播被更新的RREQ消息。6.根據權利要求3的方法，其中，所述目的節點將包含在所述RREQ消息中的第二信息附加到所創建的路由應答RREP消息中。7.根據權利要求6的方法，其中，所接收的RREP消息被轉發到對應於所述第二信息的節點。8.根據權利要求7的方法，其中，對應於所述第二信息的節點使用存儲在所述路由選擇表中的所述第二信息，來更新所接收的RREP消息。9.根據權利要求1的方法，其中，當所述目的節點是所述源節點的沿所述樹狀路由的父節點或後代節點時，所述源節點不創建所述RREQ消息。10.根據權利要求9的方法，其中，所述源節點根據樹狀路由器計算來定位所述目的節點的位置，並將數據轉發到所定位的位置。11.根據權利要求10的方法，其中，所述中間節點將其地址與所述目的節點的地址進行比較，並且當所述兩個地址不相同時，沿所述樹狀路由中繼所述數據。12.一種在包括目的節點和源節點的移動通信系統中建立從所述源節點到所述目的節點的路由的設備，所述源節點經由至少一個中間節點將RREQ消息發送到所述目的節點，所述設備包括所述源節點，用於創建路由請求RREQ消息，並且發送所創建的RREQ消息；至少一個中間節點，用於發送被更新的RREQ消息，當沿著除所述樹狀路由之外的路由接收到所述RREQ消息時，所述中間節點使用所存儲的信息來更新用於搜索反向路由的第一信息；以及所述目的節點。13.根據權利要求12的設備，其中，僅當沿著除所述樹狀路由之外的路由從後代節點接收到所述RREQ消息時，所述中間節點更新並發送所接收的RREQ消息。14.根據權利要求12的設備，其中，當沿著所述樹狀路由接收到包含所述第一信息的RREQ消息時，所述中間節點使用所存儲的信息來更新用於搜索所述反向路由的第二信息。15.根據權利要求14的設備，其中，所述中間節點將被更新的第二信息存儲到路由選擇表中。16.根據權利要求14的設備，其中，當包含在所述RREQ消息中的目的節點是所述後代節點時，所述中間節點單播被更新的RREQ消息。17.根據權利要求14的設備，其中，所述目的節點將所述RREQ消息中包含的第二信息附加到所創建的路由應答RREP消息中。18.根據權利要求17的設備，其中，所述中間節點將所接收的RREP消息轉發到對應於所述第二信息的節點。19.根據權利要求18的設備，其中，所述中間節點使用存儲在所述路由選擇表中的所述第二信息，來更新所接收的RREP消息。20.根據權利要求12的設備，其中，當所述目的節點是所述源節點的沿所述樹狀路由的父節點或後代節點時，所述源節點不創建所述RREQ消息。21.根據權利要求20的設備，其中，所述源節點根據樹狀路由器計算來定位所述目的節點的位置，並且將數據轉發到所定位的位置。22.根據權利要求21的設備，其中，所述中間節點將其地址與所述目的節點的地址進行比較，並且當所述兩個地址不相同時，沿所述樹狀路由中繼所述數據。全文摘要一種方法，用於在移動通信系統中使用樹狀拓撲通過中間節點來中繼路由請求RREQ消息，該中間節點與至少一個節點連接，該移動通信系統包含目的節點和源節點，該源節點經由至少一個中間節點將RREQ消息發送到目的節點，從而建立用於通信的最佳路由。RREQ消息是沿除樹狀路由之外的路由被接收的，並且使用它的信息來更新該第一信息。該中間節點將包含更的新第一信息的RREQ消息中繼到下一個中間節點。文檔編號H04L12/56GK1599350SQ200410076688公開日2005年3月23日申請日期2004年5月9日優先權日2003年5月9日發明者胡旭暉,劉勇,朱春暉,李明鍾申請人:三星電子株式會社,紐約城市大學