Detecting Critical Members in a Moving Group of Wireless Ad Hoc Networks

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：61

、訪客IP：3.139.104.39

姓名

張偉立(Wei-Li Chang) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

(Detecting Critical Members in a Moving Group of Wireless Ad Hoc Networks)

相關論文

★ 具多重樹狀結構之可靠性群播傳輸	★ 在嵌入式行動裝置上設計與開發跨平台Widget
★ 在 ARM 架構之嵌入式系統上實作輕量化的手持多媒體播放裝置圖形使用者介面函式庫	★ 基於網路行動裝置所設計可擴展的服務品質感知GStreamer模組
★ 針對行動網路裝置開發可擴展且跨平台之GSM/HSDPA引擎	★ 於單晶片多媒體裝置進行有效率之多格式解碼管理
★ IMS客戶端設計與即時通訊模組研發：個人資訊交換模組與即時訊息模組實作	★ 在可攜式多媒體裝置上實作人性化的嵌入式小螢幕網頁瀏覽器
★ 以IMS為基礎之及時語音影像通話引擎的實作:使用開放原始碼程式庫	★ 電子書嵌入式開發: 客制化下載服務實作, 資料儲存管理設計
★ 於數位機上盒實現有效率訊框參照處理與多媒體詮釋資料感知的播放器設計	★ 具數位安全性的電子書開發：有效率的更新模組與資料庫實作
★ 適用於異質無線寬頻系統的新世代IMS客戶端軟體研發	★ 在可攜式數位機上盒上設計並實作重配置的圖形使用者介面
★ Friendly GUI design and possibility support for E-book Reader based Android client	★ Effective GUI Design and Memory Usage Management for Android-based Services

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

無線動態隨意網絡(Mobile Ad hoc networks) 是一群節點藉由網絡傳輸連結而組成, 其中有一部份節點, 我們稱之為關節點(Articulation points), 也就是說, 在網絡中將移開關節點, 網絡將會分裂成一個以上不同的子網絡, 導致傳遞的資訊無法互相溝通. 相關文獻提出在靜態的網路(Static Networks) 之下偵測關節點, 然而在動態的網路 (Dynamic Networks)之下快速和準確的偵測關節點是一個挑戰. 這篇博士論文動機緣起於, 報章新聞報導一群人出遊, 常有走失現象, 例如: 老師帶小朋友出遊, 老人出遊, 甚至是車隊出遊, 這樣的活動由於人數多, 在管理和監控上不易, 基於此首先我們提出了區域深先搜尋法(Localized Depth First Search)來解決在動態網路下偵測關節點這個問題. 接下來考慮到省電(Power Saving)的議題, 在動態網路之下, 無線網路裝置的電量是有限的, 如何在不影響關節點偵測之下, 達到最省電的機制, 我們提出了省電搜尋法(Power Saving-LDFS), 實驗結果表示, 我們的方法在訊息負載, 偵測速度 ,電量節省上皆有較優秀的表現.

摘要(英)

The articulation points in the induced graph of a network are known to be critical in terms of maintaining the connectivity of the network as most of the routing paths between nodes in the network have to pass through them. To detect articulation points, the previous works assume the setting of static networks. However, in case when a group of people move together, their mobile devices forms a highly dynamic mobile ad hoc network and the behavior of nodes in such a network can be a challenge when it comes to detecting articulation points. In this paper, we propose a distributed algorithm, namely Localized Depth-First-Search (LDFS), to identify articulation points efficiently in mobile ad hoc networks. The algorithm sets multiple initiators to send probing packets and a bound for the hop count of the probing packets in order to improve the accuracy rate and message overhead at the same time. The simulation results show that our LDFS algorithm outperforms the other well-known protocols, which suggest that LDFS is a better solution for articulation point detection to prevent possible losses in a group of moving nodes. In second part, we proposed a Power-Saving LDFS protocol to save power of node and still maintain the connectivity of network. The performance of energy consumption is better than original case.

關鍵字(中)

★ 關節點
★ 區域深先搜尋
★ 省電

關鍵字(英)

★ depth first search
★ power saving
★ articulation points

論文目次

Abstract in Chinese i
Abstract in English ii
Acknowledgements iii
Table of Contents iv
List of Figures
vii
List of Tables
ix
List of Abbreviations x
1 Introduction
1
1.1 Contributions 3
1.1.1 Purpose 3
1.1.2 Motivation 4
1.1.3 Contributions in Brief 5
1.2 Thesis Organization 6
2 Related Work and Background Knowledge
7
2.1 Algorithms for Detecting Articulation Points 7
2.1.1 Centralized Detection Algorithm for Articulation Points
7
2.1.2 Localized Detection Algorithm for Articulation Points
8
2.2 Topology Control and Power Saving Algorithms 10
2.2.1 Homogeneous Topology Control Algorithms 12
2.2.2 Non-homogeneous Topology Control Algorithms 12
2.2.2.1 Location-based Topology Control Algorithms 13
2.2.2.2 Neighbor-based Topology Control Algorithms 14
3 Detecting Articulation Points in Mobile Networks 17
3.1 Proposed LDFS Algorithm 17
3.1.1 Localized Depth-First-Search
17
3.1.2 Data Structure and Message Format
18
3.1.3 LDFS Algorithm and Flow Chart
21
3.1.4 LDFS Optimization
26
3.1.5 Time Cost of LDFS
27
3.1.6 Algorithm Analysis
27
3.2 Simulation Results
29
3.2.1 Average Delay 31
3.2.2 Message Overhead
35
3.2.3 Correctness
37
3.3 Summary 39
4 Power Saving for LDFS Algorithm 39
4.1 Proposed PS-LDFS 41
4.1.1 Detecting Bridges Phase (DB) 43
4.1.2 Adjusting Transmitting Power Phase (ATP) 45
4.1.3 Node Serialize Trigger (NST) 48
4.1.4 Avoid Partitions and Topology Maintaining 49
4.2 Simulations Results 50
4.2.1Average Delay 52
4.2.2Energy Consumption 54
4.3 Summary 56
5. Conclusions and Future Works
57
Bibliography
58

參考文獻

Bibliography
[1] S. Saroiu, P. Gummadi, and S. Gribble, "A Measurement Study of Peer-to-Peer File Sharing Systems," in Proceedings of Multimedia Computing and Networking (MMCN), 2002.
[2] F. Buckley and M. Lewinter, A Friendly Introduction to Graph Theory, 2002.
[3] X. Liu, L. Xiao, A. Kreling, and Y. Liu, "Optimizing Overlay Topology by Reducing Cut Vertices," in Proceedings of ACM NOSSDAV, 2006.
[4] B. Awerbuch, "A New Distributed Depth-First Search Algorithm," Information Processing Letters, vol. 20, pp. 147-150, 1985.
[5]. Andrew Kreling, Yunhao Liu, Xiaomei Liu, Li Xiao. “Optimizing overlay topology by reducing cut vertices.” NOSSDAV, 17, 2006.
[6]. O. Younis, S. Fahmy, and P. Santi, "An architecture for robust sensor network communications," International Journal on Distributed Sensor Networks (IJDSN), Special issue on localized communication and topology protocols for sensor networks, 2005.
[7] W. Zhang, G. Xue, and S. Misra, "Fault-tolerant relay node placement in wireless sensor networks: problems and algorithms," in Proceedings of IEEE INFOCOM, 2007.
[8] T. Q. Qiu, E. Chan, and G. Chen, "Overlay Partition: Iterative Detection and Proactive Recovery," in Proceedings of IEEE ICC,2007.
[9] B. Krishnamurthy, S. Sen, Y. Zhang, and Y. Chen, "Sketchbased Change Detection: Methods, Evaluation, and Applications," in Proceedings of ACM SIGCOMM Internet Measurement Conference (IMC), 2003.
[10] S. Kim and A. L. N. Reddy, "Image-based Anomlay Detection Technique: Algorithm, Implementation and Effectiveness"," IEEE JSAC, 2006.
[11] N. Hu, L. E. Li, Z. M. Mao, P. Steenkiste, and J. Wang, "Locating Internet Bottlenecks: Algorithms, Measurements, and Implications," in Proceedings of ACM SIGCOMM, 2004.
[12] D. Dumitriu, E. Knightly, I. Stoica, and W. Zwaenepoel, "Denial of Service Resilience in Peer-to-Peer File Sharing Systems," in Proceedings of ACM SIGMETRICS, 2005.
[13] Carlos, Andre, Reis Pinheiro, “Social Network Analysis in Telecommunications.” John Wiley and Sons, 2011.
[14] Rosales-Hain, R. Ramanathan, “Topology control of multihop wireless networks using transmit power adjustment”. INFOCOM, 2:404 – 413, 2000.
[15] Y. Zhu and Y. Hu, "Making Peer-to-Peer Anonymous Routing Resilient to Failures," in Proceedings of IPDPS, 2007.
[16] T. Q. Qiu, E. Chan, and G. Chen, "Overlay Partition: Iterative Detection and Proactive Recovery," in Proceedings of IEEE ICC, 2007.
[17] J. Mirkovic, G. Prier, and P. Reiher, "Attacking DDoS at the Source," in Proceedings of IEEE ICNP, 2002.
[18] P. Keyani, B. Larson, and M. Senthil, "Peer Pressure: Distributed Recovery from Attacks in Peer-to-Peer Systems," in Proceedings of IFIP Workshop on Peer-to-Peer Computing, 2002.
[19] Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker, "Making Gnutella-like P2P Systems Scalable," in Proceedings of ACM SIGCOMM, 2003.
[20] Yunhao Liu, Baijian Yang, Yuan He, Hao Ren. “On The Reliability of Large-scale Distributed systems - A Topological View.” computer Networks, 53:2140–2152, 2009.
[21] M. Li, W.-C. Lee, and A. Sivasubramaniam, "DPTree: A Balanced Tree Based Indexing Framework For Peer-To-Peer Systems," in Proceedings of IEEE ICNP, 2006.
[22] L. Ramaswamy, B. Gedik, and L. Liu, "A Distributed Approach to Node Clustering in Decentralized Peer-to-Peer Networks," IEEE Transactions on Parallel and Distributed Systems, 2005.
[23]. Nicholas D. Lane, Emiliano Miluzzo, “A Survey of Mobile Phone Sensing,” A Survey of Mobile Phone Sensing 2009
[24]. R. Tarjan, “Depth First Search and Linear Graph Algorithms,” SIAM J. Comp., vol. 1, no. 2, 1972, pp. 146–60.
[25]. D. Goyal and J. Caffery, “Partitioning Avoidance in Mobile Ad Hoc Net-works using Network Survivability Concepts,” Proc. IEEE ISCC, Taormina, Italy, July 2002, pp. 553–58.
[26]. Tracy Camp*, Jeff Boleng, and Vanessa Davies, “A survey of mobility models for ad hoc network research,” Wireless Communications and Mobile Computing, Volume 2, Issue 5, pages 483–502,August 2002.
[27]. Mathew D. Penrose, “On k-connectivity for a geometric random graph,” Random Structures & Algorithms, Volume 15, Issue 2, pages 145–164,September 1999.
[28].Xiaohua Jia, Dongsoo Kim, Sam Makki, Peng-Jun Wan, Chih-Wei Yi, “Power Assignment for k-Connectivity in Wireless Ad Hoc Networks,” Journal of Combinatorial Optimization, March 2005, Volume 9, Issue 2, pp 213-222.
[29]. Suresh Singh, Mike Woo, C. S. Raghavendra, “Power-aware routing in mobile ad hoc networks,” MobiCom ’98 Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking Pages 181-190
[30]. S. Narayanaswamy, V. Kawadia, R. S. Sreenivas, and P. R. Kumar, “Power control in ad-hoc networks: Theory, architecture, algorithm and implementation of the COMPOW protocol,” in European Wireless Conference, 2002.
[31]. Penrose, M, “The longest edge of the random minimal spanning tree,” Annals Appl. Probab. 7, 2, 340–361, 1997.
[32]. Penrose, M, “Extremes for the minimal spanning tree on normally distributed points,” Advances Appl. Probab. 30, 628–639, 1998.
[33]. Dette, H. and Henze, N, “The limit distribution of the largest nearest-neighbor link in the unit d-cube,” J. Appl. Probab. 26, 67–80, 1989.
[34]. Holst, L, “On multiple covering of a circle with random arcs,” J. Appl. Probab. 16, 284–290.1980
[35]. Panchapakesan, P. and Manjunath, D, “On the transmission range in dense ad hoc radio networks,” InProceedings of IEEE Signal Processing Communication (SPCOM), 2001.
[36]. Santi, P., Blough, D., and Vainstein, F, “A probabilistic analysis for the range assignment problem in ad hoc networks,” in Proceedings of ACM Mobihoc. 212–220, 2001.
[37]. Kirousis, L., Kranakis, E., Krizanc, D., and Pelc, “Power consumption in packet radio networks,” Theoret. Comput. Sci. 243, 289–305.2000
[38].Clememti, A., Ferreira, A., Penna, P., Perennes, S.,and Sielvestri, R, “Hardness results for the power range assignment problem in packet radio networks,” in Proceedings of the 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (RANDOM/APPROX). 197–208, 1999.
[39]. Clememti, A., Ferreira, A., Penna, P., Perennes, S.,and Sielvestri, R, “The power range assignment problem in radio networks on the plane,” in Proceedings of the 17th Symposium on Theoretical Aspects of Computer Science (STACS). 651–660.2001
[40]. Clememti, A., Ferreira, A., Penna, P., Perennes, S.,and Sielvestri, R, “The minimum range assignment problem on linear radio networks,” in Proceedings of the 8th European Symposium on Algorithms (ESA). 143–154. 2000
[41]. Rodoplu, V. and Meng, T, “Minimum energy mobile wireless networks,” IEEE J. Select. Areas Comm. 17, 8, 1333–1344, 1999

指導教授

吳曉光(Eric Hsiao-kuang Wu)

審核日期

2013-8-30

推文