長鏈狀ZigBee網絡的網絡地址分配方法和路由方法
2023-04-25 07:38:41
專利名稱：：長鏈狀ZigBee網絡的網絡地址分配方法和路由方法
技術領域：
：本發明是有關於長鏈狀ZigBee網絡，且特別是有關於一種長鏈狀ZigBee網絡的網絡地址分配方法以及路由(routing)方法。
背景技術：
：在快速發展的無線傳感網絡(wirelesssensornetwork)技術中，ZigBee網絡協定是一項重要且普及的技術。ZigBee網絡協定所定義的路由方法主要可分成二種表格路由(tablerouting)與樹狀路由(treerouting)。表格路由主要是通過查表的方式來知道下一個要傳送的節點(node)。樹狀路由則是利用地址分配(addressassignment)來進行路由，採用樹狀路由的網絡都有預定的規則架構，根據地址就能知道每一個節點在網絡中的位置，因此由附近節點的地址就能決定要傳送的方向。然而這二種路由方式都有其缺點而均不適合長鏈狀網絡的使用。長鏈狀網絡就如圖l所示，其中每個圓圈代表一個節點。長鏈狀網絡的主體是由很長的骨幹網絡組成，其分支網絡的長度比較短。表格路由的方式，通常是在每一個節點上以有限的空間，來存放一個路由表(routingtable)。舉例而言，當節點A要送封包至節點B時，節點A會先查路由表有沒有存放到達節點B的路由信息。如果有，就依路由信息傳送封包。如果沒有，節點A會對下面的其他節點廣播，以詢問送封包至節點B的路徑，得到路由信息後，再把原來的封包送至節點B。這種方式的缺點是成本太高，在進行路由時，可能會一直向周圍的節點廣播，才能得到路由信息，如此可能會有很長的廣播時間，而且會造成網絡擁塞以及不必要的傳輸浪費。樹狀路由的方式是依附近節點的地址來決定路由的方向。ZigBee網絡設備支持兩種地址類型一種是64位的IEEE(InstituteofElectricalandElectronicsEngineers,即國際電氣電子工程師學會)地址，另一種是16位的網絡地址(networkaddress)。IEEE地址在所有ZigBee網絡設備之中是唯一的。16位的網絡地址則可以由使用者自定，來決定路由的信息。然而，由於網絡地址只有16位，也就是最多只能分配216個地址。網絡中每個節點只能有單一的網絡地址，而且使用樹狀路由的網絡架構(topology)必須為平衡樹(balancetree)。以最大鏈結長度(MAX—DEPTH)為5，最大下級節點數量(MAX—CHILDREN)為6的網絡架構為例，16位的網絡地址最多只能有五層長度，如圖2所示。由於全部節點太多，繪示不便，圖2僅繪示其中一部分。若以最大下級節點數量為2的平衡樹來計算，16位的網絡地址最多只能有15層的網絡鏈結長度，並不適用於鏈結長度通常會大於15的長鏈狀網絡。由上述討論可知，ZigBee網絡協定所定義的二種路由方法，表格路由和樹狀路由，都不適用於長鏈狀網絡。
發明內容本發明提供一種特別適用於長鏈狀ZigBee網絡的網絡地址分配方法，可減少封包傳輸的成本。本發明提供一種特別適用於長鏈狀ZigBee網絡的路由方法，可提升網絡路由的效能。本發明的長鏈狀ZigBee網絡包括多個集群(cluster)，每一集群包括一個集群首領(clusterheader)以及多個集群成員(clustermember)。本發明提出一種長鏈狀ZigBee網絡的網絡地址分配方法，其特點是分配一網絡地址至一長鏈狀ZigBee網絡的每一節點，其中每個網絡地址包括一集群代號(clusterID)與一節點代號(nodeID)。集群代號用以識別長鏈狀ZigBee網絡的多個集群並且用以進行集群之間的封包路由。節點代號用以識別每一集群包括的多個節點並且用以進行每一集群之內的封包路由。在本發明的一實施例中，從長鏈狀ZigBee網絡的協調器(coordinator)開始，各集群的集群代號是以遞增或遞減方式排列。每一個集群首領的節點代號設定為零，集群成員的節點代號則依照傳統的ZigBee網絡地址分配演算法進行分配。在本發明的一實施例中，上述的每一集群皆為平衡樹。每一個平衡樹可以有相同的最大鏈結長度與最大下級節點數量，也可以有各自的最大鏈結長度與最大下級節點數量。本發明另提出一種長鏈狀ZigBee網絡的路由方法，包括下列步驟。首先，使用上述的網絡地址分配方法分配各節點的網絡地址。在傳遞封包時，檢查封包的所在節點的集群代號是否等於同一封包的目的節點的集群代號。若上述兩個集群代號相等，則根據目的節點的節點代號以及一預設演算法在該集群內進行封包路由。若上述兩個集群代號不相等，則根據目的節點的集群代號在上述集群之間進行封包路由。在本發明的一實施例中，上述的預設演算法為樹狀路由演算法或表格路由演算法。在本發明的一實施例中，若封包所在節點的集群代號不等於目的節點的集群代號，而且所在節點為集群成員，則傳送封包至所在節點的上級節點(parentnode)。若封包所在節點的集群代號不等於目的節點的集群代號，而且所在節點為集群首領，則根據所在節點的集群代號與目的節點的集群代號的比較結果，傳送封包至所在節點的上級集群首領(parentclusterheader)或下級集群首領(childclusterheader)。在本發明的一實施例中，若封包所在節點的集群代號不等於目的節點的集群代號，而且所在節點為集群首領，則在集群首領之間傳送封包的原則如下。若目的節點的集群代號位於協調器的集群代號與所在節點的集群代號所限定的範圍之內，則傳送封包至所在節點的上級集群首領。反之，若目的節點的集群代號位於協調器的集群代號與所在節點的集群代號所限定的範圍之外，則傳送封包至所在節點的下級集群首領。在本發明的一實施例中，在集群首領之間傳送封包時，若某個上級集群首領無法接收封包，而且此上級集群首領的集群代號不等於封包目的節點的集群代號，則傳送封包至此上級集群首領的上級集群首領。另一方面，若某個下級集群首領無法接收封包，而且此下級集群首領的集群代號不等於封包目的節點的集群代號，則傳送封包至此下級集群首領的下級集群首領。本發明的網絡地址分配方法以及路由方法是針對長鏈狀ZigBee網絡而設計，因此特別適用於長鏈狀ZigBee網絡，可減少封包傳輸的成本，提升網絡路7由的效能。為讓本發明的上述目的、特徵和優點能更明顯易懂，以下結合附圖對本發明的具體實施方式作詳細說明，其中圖1是現有的一種長鏈狀ZigBee網絡的示意圖。圖2是現有的一種樹狀ZigBee網絡的示意圖。圖3是依照本發明一實施例的長鏈狀ZigBee網絡架構示意圖。圖4是依照本發明一實施例的網絡地址示意圖。圖5是依照本發明一實施例的長鏈狀ZigBee網絡架構示意圖。圖6是依照本發明一實施例的長鏈狀ZigBee網絡的路由方法流程圖。圖7是依照本發明一實施例的長鏈狀ZigBee網絡架構示意圖。主要元件符號說明300、500、700:長鏈狀ZigBee網絡301:協調器310、320、330:節點集群311、321、331:集群首領312、322、332:集群成員340:骨幹網絡610-670:流程圖步驟701-706:ZigBee網絡節點0x0000-0x1400:網絡節點的網絡地址具體實施例方式圖3為依照本發明一實施例的長鏈狀ZigBee網絡300示意圖。本實施例的ZigBee網絡可包括一個協調器以及多個節點集群。例如圖3的ZigBee網絡300包括協調器301以及三個集群310、320、330。每個集群包括一個集群首領以及多個集群成員，例如集群310包括集群首領311以及四個集群成員312，8集群320包括集群首領321以及四個集群成員322，集群330包括集群首領331以及四個集群成員332。每個集群的成員數量可以相同也可以不相同。所有集群首領組成了長鏈狀ZigBee網絡的骨幹網絡部分，例如集群首領311、321、以及331組成了ZigBee網絡300的骨幹網絡340。本實施例採用16位的網絡地址進行封包路由，這些網絡地址在一開始規劃ZigBee網絡時就分配給網絡中的每一個節點。如圖4所示，每一個網絡地址包括一個集群代號與一個節點代號，集群代號與節點代號各佔多少位視實際應用而定。集群代號用以識別長鏈狀ZigBee網絡的各個集群，並且用以進行各集群之間的封包路由。節點代號則用以識別每一個集群所包括的多個節點，並且用以進行每一個集群之內的封包路由。每一個節點的集群代號和該節點的集群首領相同，也就是說，同一個集群的所有節點都有相同的集群代號。不同集群的節點則有不同的集群代號。協調器有一個唯一的集群代號，和所有集群都不相同。同一個集群之內的節點各有不同的節點代號。為了能輕易判斷封包的路由方向，所有集群首領的集群代號必須組成一個嚴格遞增數歹lj(strictlyincreasingsequence)或嚴格遞減數歹ll(strictlydecreasingsequence)。若是嚴格遞增數列，協調器必須有全網絡最小的集群代號，例如協調器的網絡地址可為0x0000，離協調器越遠的集群首領分配到的集群代號就越大。反之，若是嚴格遞減數列，協調器必須有全網路最大的集群代號，離協調器越遠的集群首領分配到的集群代號就越小。如果需要更規則的順序，可將所有集群首領的集群代號設定為一個等差數列。至於節點代號的分配，可將每一個集群首領的節點代號設定為零，集群成員的節點代號則依照傳統的ZigBee網絡地址分配演算法進行分配。接下來說明本實施例的封包路由方法。以下說明請參照圖5和圖6，圖6為本實施例的長鏈狀ZigBee網絡的路由方法流程圖，圖5為用以說明圖6流程的一個ZigBee網絡範例。圖5繪示了長鏈狀ZigBee網絡500的所有節點以及各節點的網絡地址，其中的網絡地址就如圖4所示，包括6位的集群代號以及IO位的節點代號。圖6的流程從步驟610開始。首先，當需要將某一個封包傳送到某一個目的節點時，在步驟610判斷封9包目前的所在節點的集群代號是否等於欲傳送的目的節點的集群代號。如果這兩個集群代號相等，表示封包所在節點和目的節點位於同一個集群之內，例如圖5的節點0x0402以及0x0404。此時流程進入步驟620，根據目的節點的節點代號以及預設演算法在這個集群內進行封包路由。上述的預設演算法用於單一集群之內的封包路由，可以採用樹狀路由演算法或表格路由演算法。若採用樹狀路由演算法，為了簡化運算，可將每個集群都規劃為平衡樹架構，而且可將每一個平衡樹設定為具有相同的最大鏈結長度以及最大下級節點數量。這並非必要限制條件，在本發明的其他實施例中，每一個平衡樹可以有各自的最大鏈結長度以及最大下級節點數量。回到步驟610，若封包所在節點的集群代號不等於目的節點的集群代號，表示所在節點和目的節點不在同一個集群當中，例如所在節點為0x0402，而目的節點為0x0C03。此時必須藉骨幹網絡根據目的節點的集群代號進行集群之間的封包路由，流程會進入步驟630以判斷封包所在節點的種類。如果封包所在節點為一般的集群成員(非集群首領)，則流程進入步驟640，將封包傳送到目前所在節點的上級節點，例如節點0x0402會將封包傳送至節點0x0401，而節點0x0401會將封包傳送至集群首領0x0400。回到步驟630，若封包所在節點為集群首領，則流程進入步驟650，檢查目的節點的集群代號是否位於協調器的集群代號與封包所在節點的集群代號所限定的範圍之內。如果在此範圍之內，表示目的節點位於協調器與封包所在節點之間，就在步驟660將封包傳送至所在節點的上級集群首領，也就是協調器方向的前一個集群首領。反之，如果目的節點的集群代號位於此範圍之外，就在步驟670將封包傳送至所在節點的下級集群首領，也就是遠離協調器方向的下一個集群首領。舉例而言，集群首領0x0800的上級集群首領是0x0400，而下級集群首領是OxOCOO。在前面的從節點0x0402傳送封包至節點0x0C03的範例中，封包依次經過節點0x0401、0x0400、0x0800，然後到達集群首領OxOCOO。集群首領OxOCOO則依次執行步驟610與620，使用步驟620的預設演算法進行集群內路由，將封包傳送到節點OxOC03。無線傳感網絡可能應用在大範圍的自然環境中，可能會有節點損壞，損壞的節點將無法傳遞封包，為了適應此情況，本發明包括骨幹網絡的容錯(faulttolerance)機制。請參照圖7，圖7為依照本發明一實施例的長鏈狀ZigBee網絡700的示意圖。為簡單起見，圖7僅繪示ZigBee網絡700的骨幹網絡其中一部分，也就是集群首領701-706。本實施例的容錯機制為，在集群首領之間傳送封包時，如果某一個上級集群首領無法接收封包，而且這個上級集群首領的集群代號不等於封包目的節點的集群代號，就將封包傳送到這個上級集群首領的上級集群首領。同理，如果某一個下級集群首領無法接收封包，而且這個下級集群首領的集群代號不等於封包目的節點的集群代號，就將封包傳送到這個下級集群首領的下級集群首領。例如圖7所示，原本將封包從集群首領702傳送到集群首領704，如果集群首領704因故無法接收封包，就直接將封包從集群首領702傳送到集群首領705。為達到容錯的目的，每個集群首領的無線傳輸範圍在靠近協調器的方向必須涵蓋至少兩個上級集群首領，在遠離協調器的方向也必須涵蓋至少兩個下級集群首領。綜上所述，本發明的網絡地址分配方法以及路由方法是針對長鏈狀ZigBee網絡的架構而設計，因此特別適用於長鏈狀ZigBee網絡，尤其是鏈結長度超過15層的長鏈狀網絡。本發明可減少封包傳輸的成本，提升網絡路由的效能。雖然本發明已以較佳實施例揭示如上，然其並非用以限定本發明，任何本領域技術人員，在不脫離本發明的精神和範圍內，當可作些許的修改和完善，因此本發明的保護範圍當以權利要求書所界定的為準。權利要求1.一種長鏈狀ZigBee網絡的網絡地址分配方法，其特徵在於分配一網絡地址至一長鏈狀ZigBee網絡的每一節點，其中該網絡地址包括一集群代號與一節點代號，該集群代號用以識別該長鏈狀ZigBee網絡的多個集群並且用以進行該些集群之間的封包路由，該節點代號用以識別上述每一集群包括的多個節點並且用以進行上述每一集群之內的封包路由。2.如權利要求1所述的長鏈狀ZigBee網絡的網絡地址分配方法，其特徵在於，該長鏈狀ZigBee網絡的所有集群首領的集群代號組成一嚴格遞增數列或一嚴格遞減數列。3.如權利要求2所述的長鏈狀ZigBee網絡的網絡地址分配方法，其特徵在於，若該些集群代號組成該嚴格遞增數列，則該長鏈狀ZigBee網絡的協調器的集群代號小於該嚴格遞增數列的每一集群代號，若該些集群代號組成該嚴格遞減數列，則該協調器的集群代號大於該嚴格遞增數列的每一集群代號。4.如權利要求2所述的長鏈狀ZigBee網絡的網絡地址分配方法，其特徵在於，該些集群代號組成一等差數列。5，如權利要求2所述的長鏈狀ZigBee網絡的網絡地址分配方法，其特徵在於，上述每一集群首領的節點代號皆為零。6.如權利要求1所述的長鏈狀ZigBee網絡的網絡地址分配方法，其特徵在於，上述每一節點的集群代號和該節點的集群首領相同。7.如權利要求1所述的長鏈狀ZigBee網絡的網絡地址分配方法，其特徵在於，上述每一集群皆為平衡樹。8.如權利要求7所述的長鏈狀ZigBee網絡的網絡地址分配方法，其特徵在於，上述每一平衡樹皆有相同的最大鏈結長度與最大下級節點數量。9.一種長鏈狀ZigBee網絡的路由方法，其特徵在於包括(a)分配一網絡地址至一長鏈狀ZigBee網絡的每一節點，其中該網絡地址包括一集群代號與一節點代號，該集群代號用以識別該長鏈狀ZigBee網絡的多個集群，該節點代號用以識別上述每一集群包括的多個節點；(b)檢查一封包的所在節點的集群代號與該封包的目的節點的集群代號是否相同；(C)若該所在節點的集群代號等於該目的節點的集群代號，則根據該目的節點的節點代號以及一預設演算法在該集群內進行該封包的路由；以及(d)若該所在節點的集群代號不等於該目的節點的集群代號，則根據該目的節點的集群代號在該些集群間進行該封包的路由。10.如權利要求9所述的長鏈狀ZigBee網絡的路由方法，其特徵在於，該長鏈狀ZigBee網絡的所有集群首領的集群代號組成一嚴格遞增數列或一嚴格遞減數列。11.如權利要求10所述的長鏈狀ZigBee網絡的路由方法，其特徵在於，若該些集群首領的集群代號組成該嚴格遞增數列，則該長鏈狀ZigBee網絡的協調器的集群代號小於該嚴格遞增數列的每一集群代號，若該些集群首領的集群代號組成該嚴格遞減數列，則該協調器的集群代號大於該嚴格遞增數列的每一集群代號。12.如權利要求10所述的長鏈狀ZigBee網絡的路由方法，其特徵在於，該些集群首領的集群代號組成一等差數列。13.如權利要求10所述的長鏈狀ZigBee網絡的路由方法，其特徵在於，上述每一集群首領的節點代號皆為零。14.如權利要求9所述的長鏈狀ZigBee網絡的路由方法，其特徵在於，上述每一節點的集群代號和該節點的集群首領相同。15.如權利要求9所述的長鏈狀ZigBee網絡的路由方法，其特徵在於，上述每一集群皆為平衡樹。16.如權利要求15所述的長鏈狀ZigBee網絡的路由方法，其特徵在於，上述每一平衡樹皆有相同的最大鏈結長度與最大下級節點數量。17.如權利要求9所述的長鏈狀ZigBee網絡的路由方法，其特徵在於，該預設演算法為樹狀路由演算法或表格路由演算法。18.如權利要求9所述的長鏈狀ZigBee網絡的路由方法，其特徵在於，步驟(d)包括(dl)若該所在節點的集群代號不等於該目的節點的集群代號，而且該所在節點為集群成員，則傳送該封包至該所在節點的上級節點；以及(d2)若該所在節點的集群代號不等於該目的節點的集群代號，而且該所在節點為集群首領，則根據該所在節點的集群代號與該目的節點的集群代號的比較結果，傳送該封包至該所在節點的上級集群首領或下級集群首領。19.如權利要求18所述的長鏈狀ZigBee網絡的路由方法，其特徵在於，步驟(d2)包括(d21)若該目的節點的集群代號位於該長鏈狀ZigBee網絡的協調器的集群代號與該所在節點的集群代號所限定的範圍之內，則傳送該封包至該上級集群首領；以及(d22)若該目的節點的集群代號位於該協調器的集群代號與該所在節點的集群代號所限定的範圍之外，則傳送該封包至該下級集群首領。20.如權利要求19所述的長鏈狀ZigBee網絡的路由方法，其特徵在於，步驟(d21)包括若該上級集群首領無法接收該封包，而且該上級集群首領的集群代號不等於該目的節點的集群代號，則傳送該封包至該上級集群首領的上級集群首領；而且步驟(d22)包括若該下級集群首領無法接收該封包，而且該下級集群首領的集群代號不等於該目的節點的集群代號，則傳送該封包至該下級集群首領的下級集群首領。全文摘要本發明提供一種長鏈狀ZigBee網絡的網絡地址分配方法與路由方法。上述路由方法的步驟如下。首先，分配網絡地址至一長鏈狀ZigBee網絡的每一節點，其中每個網絡地址包括一集群代號與一節點代號。集群代號用以識別長鏈狀ZigBee網絡的多個集群，節點代號用以識別每一集群包括的多個節點。在傳遞封包時，檢查封包的所在節點與目的節點是否位在同一集群。若位在同一集群，則根據目的節點的節點代號以及一預設演算法在該集群內進行封包路由。若不在同一集群，則根據目的節點的集群代號在上述集群之間進行封包路由。文檔編號H04L12/56GK101459586SQ200710186598公開日2009年6月17日申請日期2007年12月11日優先權日2007年12月11日發明者劉永之,方華韋申請人:財團法人資訊工業策進會