2009-10-02

Distributed Borrowing Addressing Scheme for ZigBee/IEEE 802.15.4 Wireless Sensor Networks

主旨:
在ZigBee網路中,因為有限的樹深與樹寬在分散式位址分配機制,使得新進的節點受到這些限制而無法獲取網路位址,本文針對此問題提出Distributed Borrowing Addressing Scheme來改善此問題。

------------------------------

解法:
當新的節點要加入網路時會先Scanning網路範圍中所有的點為父節點的候選者,選定父節點後若父節點有位址可分配則立即分配位址,反之若因受到Rm, Cm, Lm而無法獲取網路位址時,其父節點會發送一個借貸需求給其父節點的鄰居向他們借貸一個連續區塊的位址,分配給此新加入網路的節點,而解決原先因受到DAAM參數限制而無法獲取位的問題。



------------------------------

結論:
針對此方法在模擬圖表中可以看出有大大的改善網路位址分配失敗問題並增加網路的覆蓋範圍但此方法必須而外增加借貸路由表和原先的DAAM比較起來在路由時必定要額外付出極大的成本,但作者在這方面並未提供任何資訊。

USING GAME THEORY TO ANALYZE WIRELESS AD HOC NETWORKS

主旨:
賽局理論主要利用以公式化的數學模型來研究參與者間彼此競爭或合作的狀態,而在各種無線隨意網路相互的影響可模擬為一個遊戲。此模擬分析可使得現有的協定和資源管理劃,及設計誘導於一個平衡機制,鼓勵個人用戶不要有自私的行為。

------------------------------

結論:

由於無線Ad Hoc Networks有複雜的移動性和傳輸模式,再加上動態拓撲和不可預測的連線品質,利用數學應用分析無線Ad Hoc Networks,顯示此分析大大的幫助了解這個高度動態及分散式網路環境中節點之間複雜的相互作用,且針對不同的Ad Hoc Networks協定層,提出各種轉換方法將問題轉換到GAME THEORY上,並建議使用無線媒介隨機存取技術獲得最大產量和發展強有力的技術來處理節點自私行為。

Hybrid Address Configuration for Tree-based Wireless Sensor Networks

主旨:
  在ZigBee網路中,若有新的節點要加入網路中,常常因為某些原因致使網路位址獲取失敗,作者在此篇paper中針對樹狀架構的ZigBee網路使用分層架構方法來解決無法獲取位址的問題。

問題:
  在ZigBee網路中,如果有新的節點要加入網路中,通常是使用DAAM機制新增網路位址但往往在新增節點時候受到Cm, Rm, Lm等參數所限制,致使位址獲取失敗。

解法:
  在此篇paper中作者首先提出Prime Numbering Address Allocation (PNAA),此方法是利用質因數關係來建立樹的架構,但作者發現此方法所建立的樹是左傾樹且和DAAM及方法極為相近,而後提出另一種混合式的方法hybrid address assignment(HAA),此方法用分層式架構來解決無法獲取位址的問題,其架構的第一層是以PNAA為主而第二層是以DAAM為主,這種方法除了改善位址無法獲取的問題,而且令我們訝異的是一般來說混合式的方法通常不會比較好但在這篇paper中卻出乎我們意料,。

2009-06-22

Two-Way Beacon Scheduling in ZigBee Tree-Based Wireless Sensor Networks

主旨:
broadcast和multicast是反向的運作,在ZigBee Tree-Based Wireless Sensor Networks中資料的上傳或是下載並定會受到原設計的影響造成通訊的延遲,因此此篇paper修改original superframe structure及Two-Way Beacon Scheduling的模式可大幅改善通訊延遲並降低網路中的干擾。

------------------------------------------------------------

解法:
將superframe分為多個active portions證明這是一個著色問題。

提出3點觀察:
1.Assigning upstream and downstream slots simultaneously can achieve lower delay than assigning upstream and downstream slots separately.
2.Suppose that routers Ri and Rj have indirect interference because they have some common end devices.If some end devices can be reconnected, then the indirect interference relation between Ri and Rj may be removed.
3.When selecting slots, a router with more interference neighbors should select its slots earlier.

演算法部分:
首先提出2種貪婪排程模擬比較。
上傳下載分別執行不同演算:FindUpSlot(v)和FindDnSlot(v)

FindUpSlot(v):

1.leaf node tu(v) = 0;non-leaf node tu(v) = max child+1
2.Let N(v) be the set of nodes that have direct or indirect interference with v and have received slots.
3.temp = tu(v) mod k is a feasible slot for v by examining the slots used by nodes in N(v).
(a)If there exists a v'∈N(v) such that v' and v have direct interference and su(v) = temp or sd(v) = temp, then the slot temp is not feasible for v.
(b)If there exists a v'∈N(v) such that v' and v have indirect interference and su(v) = temp or sd(v) = temp, then we will call procedure RemoveIndInt(v',v) to see if such interference can be removed.

FindDnSlot(v) :

1.leaf node td(v) = k - 1;non-leaf node td(v) = min child − 1
2和3同上

RemoveIndInt(v',v):

step 1:
Indirect interference appears when there is a common neighbor x of v’ and v.
If x is a router : ignored.
If x is an end device : try to associated x with another router
say w, other than v’ and v.
slots su(w) and sd(w):have to make sure this does not cause new interference
Otherwise: step 2

step 2:
step 1 allows us to reassociate x to another router to remove the interference
a positive response will be replied by this procedure
otherwise: a negative response will be replied

------------------------------------------------------------

結論:
modify the original superframe structure
define a two-way beacon scheduling (TBS) problem
propose a centralized algorithm to solve the TBS problem
the algorithm can effectively reduce the number of interference neighbors and thus decrease the network latency

2009-05-06

Grouping Strategy for Solving Hidden Node Problem in IEEE 802.15.4 LR-WPAN心得

主旨:

在802.15.4中存在著hidden node問題,此問題發生率高達41%,但為什麼不用RTS/CTS解決hidden node呢?因為RTS/CTS會增加額外的控制所需電源故不使用。因此在不能使用RTS/CTS的情況下以分組策略解決此問題並大大改善整個系統效能。

------------------------------

解法:

分組:node依據hidden node的關係並且區分每個組傳輸時期。

所以比Standard-H省電只要是因避免hidden node problem而比Standard-NH省電主要是因分組傳輸。
分組4步驟解決HNC:
1.hidden node的發現:先將不相連通的node設為hidden node 。
2.辨別是否為hidden:因CC和NHC碰撞關係不同加以辨別 。
3.群組分配:利用所提出的group algorithm,區分個群組確保不會有hidden node。
4.頻寬分配:以群組內node個數分配頻寬。
並提出最多只需5個group便能覆蓋一個網路的論點,並且證明...。

此5個group內的node相互有hidden的關係,但group之間不一定會有hidden的問題。

------------------------------

結論:


此方法特色主要為下列:
1.resolving the hidden node problem
2.alleviating the violent contentions
3.improving the network performance
4.reducing the power consumptions

2000-01-02

Paper list

Zigbee
  1. Anis Koubâa, André Cunha, Mário Alves, and Eduardo Tovar, "TDBS: a time division beacon scheduling mechanism for ZigBee cluster-tree wireless sensor networks," Real-Time Systems, vol. 40, pp. 321-354, October 2008.
  2. Bing Han and Gwendal Simon, "Optimizing Multi-hop Queries in ZigBee Based Multi-sink Sensor Networks," Lecture Notes In Computer Science, Vol. 5408, pp. 294-305, 2009.
  3. Chia-Hung Tsai, Meng-Shiuan Pan, Yi-Chen Lu and Yu-Chee Tseng, "Self-Learning Routing for ZigBee Wireless Mesh Networks, "
  4. Jaehyuk Jang Kwanghun Han Sunghyun Choi, "Adaptive Power Saving Strategies for IEEE 802.16e Mobile Broadband Wireless Access," Asia-Pacific Conference on Communications, 2006. APCC '06.
  5. Jin-Woo Kim, Jihoon Kim, and Doo-Seop Eom, "Multi-Dimensional Channel Management Scheme to Avoid Beacon Collision in LR-WPAN," IEEE Transactions on Consumer Electronics, vol. 54, pp. 396-404, 2008.
  6. Kenneth L. Stanwood and Stanley Wang, "IEEE Standard 802.16: A Technical Overview of the WirelessMAN™ Air Interface for Broadband Wireless Access," IEEE Communications Magazine, June 2002.
  7. Lain-Jinn Hwang, Shiann-Tsong Sheu, Yun-Yen Shih, and Yen-Chieh Cheng, "Grouping Strategy for Solving Hidden Node Problem in IEEE 802.15.4 LR-WPAN," Proceedings of the First International Conference on Wireless Internet, pp. 26-32, July 2005.
  8. Li-Hsing Yen and Wei-Ting Tsai, "The Room Shortage Problem of Tree-Based ZigBee/IEEE802.15.4 Wireless Networks," Computer Communications, October 2009.
  9. Li-Hsing Yen, Yee Wei Law, and Marimuthu Palaniswami, "Risk-aware beacon scheduling for tree-based ZigBee/IEEE 802.15.4 wireless networks," Fourth International Wireless Internet Conference (WICON), Hawaii, USA, Nov. 2008.
  10. Li-Hsing Yen and Wei-Ting Tsai, "Flexible address configurations for tree-based ZigBee/IEEE 802.15.4 wireless networks," The 22nd IEEE Int'l Conf. on Advanced Information Networking and Applications (AINA 2008), Okinawa, Japan, Mar. 2008, pp. 395-402.
  11. Lun-Wu Yeh, Meng-Shiuan Pan and Yu-Chee Tseng, "Two-Way Beacon Scheduling in ZigBee Tree-Based Wireless Sensor Networks," IEEE International Conference on Sensor Networks, Ubiquitous and Trustworthy Computing, 2008,IEEE SUTC, 11-13 June 2008 Page(s):130 – 137.
  12. Meng-Shiuan Pan, Chia-Hung Tsai, Yu-Chee Tseng, "The Orphan Problem in ZigBee Wireless Networks," IEEE Transactions on Mobile Computing, 12 Mar. 2009. IEEE computer Society Digital Library.
  13. M.-S. Pan, H.-W. Fang, Y.-C. Liu, and Y.-C. Tseng, "Address Assignment and Routing Schemes for ZigBee-Based Long-Thin Wireless Sensor Networks," IEEE Vehicular Technology Conference, pp. 173-177, 2008.
  14. R.Burda and C.Wietfeld, "A Distributed and Autonomous Beacon Scheduling Algorithm for IEEE 802.15.4/ZigBee Networks," IEEE Internatonal Conference on Mobile Adhoc and Sensor Systems, Oct. 2007 , page(s): 1-6.
  15. Sungjin Park, Eun Ju Lee, Jae Hong Ryu, Seong-Soon Joo, and Hyung Seok Kim, "Distributed Borrowing Addressing Scheme for ZigBee/IEEE 802.15.4 Wireless Sensor Networks," ETRI Journal, vol.31, no.5, Oct. 2009, pp.525-533.
  16. Wai-Hong Tam and Yu-Chee Tseng, “Joint Multi-Channel Link Layer and Multi-Path Routing Design for Wireless Mesh Networks,” IEEE International Conference on Computer Communications,INFOCOM 2007.
  17. Y.-C. Tseng and M.-S. Pan, "A Lightweight Network Repair Scheme for Data Collection Applications in ZigBee WSNs," IEEE Communications Letters, Vol. 13 , Issue 9 , September 2009, Pages: 649-651.
  18. Y.-C. Tseng and M.-S. Pan, "Quick Convergecast in ZigBee Beacon-Enabled Tree-Based Wireless Sensor Networks," Computer Communications, Vol. 31, No. 5, Mar. 2008, pp. 999-1011.
  19. Y.-C. Tseng and M.-S. Pan, “Quick convergecast in ZigBee/IEEE 802.15.4 tree-based wireless sensor networks, " in ACM Intl Workshop on Mobility Management and Wireless Access, Terromolinos, Spain, Oct. 2006, pp. 60–66.
  20. Yu Gu, Hengchang Liu and Baohua Zhao, "Target Coverage With QoS Requirements in Wireless Sensor Networks, " The 2007 International Conference on Intelligent Pervasive Computing, Oct. 2007, page(s): 35-38.
  21. Yu-Kai Huang, Ai-Chun Pang, Pang-Feng Liu and Wei-Ni Chu, "NAT-ZigBee: NAT-based Address Assignment for Scalable ZigBee Networks," IEEE INFOCOM 2010.

Coverage
  1. Jung-Eun Kim, Man-Ki Yoon, Junghee Han and Chang-Gun Lee, "Sensor Placement for 3-Coverage with Minimum Separation Requirements," Lecture Notes in Computer Science, Vol. 5067, 2008.
  2. Manju Chaudhary and Arun K Pujari, "Q-Coverage Problem in Wireless Sensor Networks," Proceedings of the 10th International Conference on Distributed Computing and Networking, Vol. 5408, pp. 325 - 330 , 2009.
  3. M. Cardei, M. T. Thai, Y. Li, and W. Wu, "Energy-Efficient Target Coverage in Wireless Sensor Networks, " in IEEE Infocom, 2005, pp.1976–1984.
  4. M. Hefeeda and M. Bagheri, "Randomized k-Coverage Algorithms for Dense Sensor Networks," in Proc. of INFOCOM 2007, 2007, pp. 2376–2380.
  5. Y. Li and S. Gao, “Designing k-Coverage Schedules in Wireless Sensor Networks,” JCO, vol. 15, pp. 127–146, 2008.
  6. Yu Gu, Hengchang Liu and Baohua Zhao, "Target Coverage With QoS Requirements in Wireless Sensor Networks," The 2007 International Conference on Intelligent Pervasive Computing, 2007 , Volume , Issue , 11-13 Oct. 2007 Page(s):35 - 38.
  7. Li-Hsing Yen, C. W. Yu, and Yang-Min Cheng, "Expected k-coverage in wireless sensor networks," Ad Hoc Networks, Vol. 5, No. 4, pp. 636-650, Sept. 2006.