Please use this identifier to cite or link to this item: http://cuir.car.chula.ac.th/handle/123456789/28136
Title: A physicomimetics desynchronization algorithm without global time knowledge for wireless sensor networks
Other Titles: ขั้นตอนวิธีการไม่ประสานเวลาเลียนแบบหลักการทางฟิสิกส์โดยปราศจากความรู้ทางเวลาแบบครอบคลุมสำหรับเครือข่ายตัวรับรู้ไร้สาย
Authors: Supasate Choochaisri
Advisors: Chalermek Intanagonwiwat
Other author: Chulalongkorn University. Faculty of Engineering
Advisor's Email: intanago@cp.eng.chula.ac.th
Subjects: Time division multiple access
Data transmission systems
Synchronization
Wireless sensor nodes
Wireless sensor networks
Issue Date: 2011
Publisher: Chulalongkorn University
Abstract: Desynchronization is useful for scheduling nodes to perform tasks at different time. This property is desirable for resource sharing, Time Division Multiple Access (TDMA) scheduling, and data transmission collision avoiding. However, to desynchronize nodes in wireless sensor networks is difficult due to several limitations. In this dissertation, we focus on desynchronization for resource-limited wireless sensor networks that resource-limited sensor nodes lack global time knowledge (\\textit{i.e.}, clocks are not synchronized). We propose a novel physicomimetics desynchronization algorithm to organize all accesses to a shared resource to be collision-free and even equitable. Inspired by robotic circular formation and Physics principle, the proposed algorithm creates an artificial force field for wireless sensor nodes. Each neighboring node has artificial forces to repel other nodes to perform tasks at different time phases. Nodes with closer time phases have stronger forces to repel each other in the time domain. Each node adjusts its time phase proportionally to total received forces. Once the total received forces are balanced, nodes are desynchronized. We evaluate our desynchronization algorithm on TOSSIM, a simulator for wireless sensor networks and evaluate on real hardware devices running TinyOS. The evaluation results indicate that the proposed algorithm is stable, scales much better than existing approaches, and incurs significantly lower desynchronization error.
Other Abstract: การไม่ประสานเวลามีประโยชน์ในการจัดการให้โหนดในเครือข่ายทำงานที่เวลาต่างกันซึ่งเป็นคุณสมบัติที่ต้องการสำหรับการจัดสรรทรัพยากรการจัดลำดับการเข้าถึงสื่อกลางแบบแบ่งตามเวลา และการหลีกเลี่ยงการส่งข้อมูลชนกัน อย่างไรก็ตามเป็นการยากที่จะทำให้โหนดในเครือข่ายตัวรับรู้ไร้สายไม่ประสานเวลากันเนื่องจากมีข้อจำกัดหลายประการ ในวิทยานิพนธ์นี้ผู้วิจัยมุ่งเน้นไปที่การไม่ประสานเวลาสำหรับเครือข่ายตัวรับรู้ไร้สายซึ่งมีทรัพยากรจำกัดที่ปราศจากความรู้ทางเวลาแบบครอบคลุม (นาฬิกาของโหนดไม่มีการประสานเวลา) ผู้วิจัยได้นำเสนอขั้นตอนวิธีการใหม่สำหรับการไม่ประสานเวลาโดยเลียนแบบหลักการทางฟิสิกส์เพื่อจัดระเบียบการเข้าถึงทรัพยากรที่ใช้ร่วมกันอย่างเท่าเทียมกันและเพื่อลดการชนกันของการส่งสัญญาณไร้สาย ขั้นตอนวิธีการที่นำเสนอทำการสร้างสนามแรงประดิษฐ์สำหรับโหนดตัวรับรู้ไร้สายซึ่งได้รับแรงบันดาลใจจากการจัดรูปแบบวงกลมในวิทยาการหุ่นยนต์และหลักการทางฟิสิกส์ โหนดแต่ละตัวในเครือข่ายจะส่งแรงประดิษฐ์ไปผลักโหนดอื่นให้ทำงานที่เฟสเวลาแตกต่างกัน คู่โหนดที่อยู่ในเฟสเวลาใกล้กันจะมีแรงกระทำต่อกันมากเพื่อผลักคู่โหนดให้ห่างออกจากกันในโดเมนทางเวลา แต่ละโหนดปรับเฟสเวลาเป็นสัดส่วนตามแรงรวมที่ได้รับ เมื่อแรงรวมที่ได้รับสมดุลแล้วโหนดต่างๆจะอยู่ในสภาวะไม่ประสานเวลา ผู้วิจัยทำการประเมินผลการทดลองของขั้นตอนวิธีการไม่ประสานเวลาที่นำเสนอบนทอซซิมซึ่งเป็นเครื่องจำลองสำหรับเครือข่ายตัวรับรู้ไร้สาย และได้ทำการทดลองกับอุปกรณ์จริงซึ่งทำงานด้วยระบบปฏิบัติการไทนี่โอเอส ผลจากการทดลองแสดงให้เห็นว่าขั้นตอนวิธีการไม่ประสานเวลาเลียนแบบหลักการทางฟิสิกส์ที่นำเสนอนั้นมีสถียรภาพในการทำงาน รองรับการปรับขนาดของเครือข่ายดีกว่าวิธีการอื่นมาก และก่อให้เกิดความผิดพลาดในการไม่ประสานเวลาน้อยกว่าวิธีการอื่นอย่างมีนัยสำคัญ
Description: Thesis (Ph.D.)--Chulalongkorn University, 2011
Degree Name: Doctor of Philosophy
Degree Level: Doctoral Degree
Degree Discipline: Computer Engineering
URI: http://cuir.car.chula.ac.th/handle/123456789/28136
Type: Thesis
Appears in Collections:Eng - Theses

Files in This Item:
File Description SizeFormat 
supasate_ch.pdf2.94 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.