針對樹狀家庭網路設計問題的演算法

Abstract

家庭網路的發展越來越受到重視，其傳輸的技術有許多選擇。由於Zigbee擁有低能源消耗、低資料傳輸率、低成本等特性，因此適合當作家庭網路用於信號控制與感測的傳輸技術。該技術是由IEEE 802.15.4與Zigbee聯盟共同制定。然而IEEE 802.15.4規格書中把路由與網路構成協定交由網路設計者自行設計，因此我們針對樹狀Zigbee網路，考量HEIGHT與CHILDREN等拓撲結構特性上的限制，設計出一個適用於家庭網路的網路建置演算法。此為附限制的最小生成樹(Constrained Minimal Spanning Tree)的問題，我們從兩個不同的角度設計：(1)適用於樹根能夠掌握整體拓撲環境為前提的集中式演算法，透過修改著名的Prim演算法達成，可用於網路重建時期；(2)適用於拓撲環境不明朗的分散式演算法，透過修改Zigbee規格的Link連結流程達成，可用於網路初建時期。經過實驗結果分析，兩個不同角度所設計的集中式與分散式演算法皆可達到80%以上的建網成功率，並且平均link連通率也可達0.7以上，確實能建立不錯且符合需求的樹狀家庭網路。

Home Network is more popular. Zigbee has many characteristics like low energy- consumed, low data transmission rate and low cost, so is one of many transmission technologies for Home network. This technology was developed by IEEE 802.15.4 and Zigbee Alliance. Because the IEEE 802.15.4 specification leave the routing and network formation protocol to network designers, we focus on tree-based Zigbee network, take two topology constraints (HEIGHT and CHILDREN) into account, then design algorithms to solve home network formation problem. This is Constrained Minimal Spanning Tree Problem (CMST), we design in two different aspects. (1) Centralized Algorithm, which is modified from Prim Algorithm, can be applied when the period of rebuilding network; root must know well all nodes of topology. (2) Decentralized Algorithm, which is modified from link association procedure of Zigbee specification, can be applied when the period of initializing network; the topology is unknown for every node. According to our experiment analysis, both algorithms can yield more than 80% completion rate of network formation and average link association probability is higher than 0.7. Both algorithms actually can build well tree-based home network.