ZigBee網路之捷徑式樹狀路由改進演算法

An Improved Shortcut Tree Routing Algorithm of ZigBee Network

范世安(Shih-an Fan)

指導教授 ： 李清坤

大同大學/電機資訊學院/通訊工程研究所/碩士(2008年)

摘要

ZigBee是以IEEE 802.15.4為基礎所制定的無線網路規格。是一種短矩離(一般為100公尺以內)、低傳輸率(250 kbps)、低成本以及低能量消耗的無線感測網路(Wireless Sensor Network, WSN)傳輸技術。其主要應用於如電表、溫濕度等各種數據的監測、遠端監控、家用設備的控制、工業以及家庭的設備自動化等。
ZigBee相關的研究中，降低成本與減少耗能一直都是重要的研究目的之一，而本文的研究主題為藉由改進路由方式達到減少耗能與減少延遲時間的效果。對於ZigBee使用的樹狀路由法，當一個準備傳送資料的節點而言，它傳送資料的路徑只會依照其原樹狀拓樸的結構進行傳送，儘管目的地節點在實際上的位置離傳送節點非常近。而為了解決這個問題，Taehong Kim, Daeyoung Kim, Noseong Park*, Seong-eun Yoo, Tomás Sánchez López五位共同提出了利用鄰點表(neighbor table)達到減少ZigBee使用的樹狀路由法的路由成本的捷徑式樹狀路由演算法(Shortcut Tree Routing Algorithm)。此方法是利用鄰點表內記錄的路由器資料計算出個別的路由成本，找出最短路徑，達到減少傳送的總跳點數。它是個具有實用價值的路由法，但它依然有可以改進的部分。由於ZigBee是一種低成本、低複雜度與有限資源的裝置，其計算能力是有限的，過大的鄰點表在計算上也很容易造成延遲。
為了得到更好的功效，本文將分析捷徑式樹狀路由法在不同環境下的效率之間的差異，並提出一套優化鄰點表的規則。依照模擬結果，鄰點表優化後的捷徑式樹狀路由改進演算法在減少傳送路徑的總跳點數方面不但可以的到更穩定的效果，同時在不同的環境下整體效率皆有4% ~ 10%以上的提升，並且達到減少耗能與減少延遲時間的效果。

關鍵字

樹狀路由法 ； 鄰點表

並列摘要

ZigBee is a wireless network standard based on IEEE 802.15.4. It is a wireless sensor network technology that the main characteristics is low transmission range (usually less than 100 meters), low data rate (250 kbps), low price and low power consumption. ZigBee is expected to use in light meter sensor, temperature and humidity sensor, remote monitoring, home control, and industrial automation.
To reduce the costs and energy consumption always is one of the most important purposes about the research correlated with ZigBee. The main subject of this paper is to reduce energy consumption and latency by reformed the routing algorithm. For the tree routing of ZigBee, when a nodes went to transmitting a packet that will follow the tree topology to the destination even if the destination is located nearby. In order to solve this problem, Taehong Kim, Daeyoung Kim, Noseong Park*, Seong-eun Yoo and Tomás Sánchez López propose the shortcut tree routing algorithm to reduce the routing cost of ZigBee tree routing by using neighbor table. This algorithm can find the shortest path by compute the routing cost for all of router that stored in neighbor table, and transmit the packet to the neighbor router that can reduce the hop count of transmission. It is a useful routing algorithm, but not perfect. Since the characteristics of Zigbee are low price, low complexity, and limited resources, it has limited capability of compute. So it may be effect delay by compute the routing cost that if neighbor table store overmuch router’s information.
In order to get better efficiency, this paper analyzes the difference of efficiency that use shortcut tree routing between different conditions, and proposes an optimized neighbor table algorithm. The simulation results show that our improved shortcut tree routing algorithm can achieve more stable and better efficiency then the previous shortcut tree routing algorithm. For our various test environments, the proposed algorithm can improve the hop counts by 4 to 10 percent, and as a result can achieve benefit of reducing energy consumption and latency.

並列關鍵字

ZigBee ； Tree routing ； Neighbor Table

參考文獻

[4]A. Viswanathan, T. E. Boult, “Power conservation in ZigBee networks using temporal control,” in Proc. IEEE International Symposium on Wireless Pervasive Computing, San Juan, Puerto Rico, Feb. 2007.

[5]N. C. Liang, P. C. Chen, T. Sun, G. Yang, L. J. Chen, M. Gerla, “Impact of node heterogeneity in ZigBee mesh network routing,” in Proc. IEEE International Conference on Systems, Man, and Cybernetics, Taipei, Taiwan, Oct. 2006, pp. 187–191.

[7]G. Ding, Z. Sahinoglu, P. Orlik, J. Zhang, B. Bhargava, ”Tree-based data broadcast in IEEE 802.15.4 and ZigBee networks,” IEEE Transactions on Mobile Computing, ISSN: 1536-1233, vol. 5, no. 11, pp. 1561-1574, Nov. 2006.

[9]J. S. Lee, “Performance evaluation of IEEE 802.15.4 for low-rate wireless personal area networks,” IEEE Transactions on Consumer Electronics, ISSN: 0098-3063, vol. 52, no. 3, pp. 742–749, Aug. 2006.

[10]K. K. Lee, S. H. Kim, H. S. Park, “Cluster label-based ZigBee routing protocol with high scalability,” in Proc. Second International Conference on Systems and Networks Communications (ICSNC), Cap Esterel, Aug. 2007.