Chulalongkorn University Theses and Dissertations (Chula ETD)

อัลกอริทึมควบคุมความหนาแน่นบนพื้นฐานเซตครอบคลุมสำหรับปัญหาครอบคลุมในระบบเครือข่ายตัวรับรู้แบบไร้สาย

Other Title (Parallel Title in Other Language of ETD)

A set cover-based density control algorithm for coverage problems in wireless sensor networks

Year (A.D.)

2007

Document Type

Thesis

First Advisor

เฉลิมเอก อินทนากรวิวัฒน์

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

วิศวกรรมศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิศวกรรมคอมพิวเตอร์

DOI

10.58837/CHULA.THE.2007.1359

Abstract

ระบบเครือข่ายตัวรับรู้แบบไร้สายเป็นระบบเครือข่ายชนิดหนึ่งที่ประกอบไปด้วยสถานีตัวรับรู้ไร้สายขนาดเล็กที่มีแหล่งกำเนิดพลังงานสำหรับใช้ในการทำงานอยู่อย่างจำกัด ดังนั้นเพื่อที่จะขยายระยะเวลาการทำงานของระบบให้อยู่ได้นานขึ้นจึงจำเป็นที่จะต้องมีกระบวนการบางอย่างในการช่วยลดปริมาณการใช้พลังงานของระบบให้น้อยลง วิทยานิพนธ์นี้ได้นำเสนออัลกอริทึมควบคุมความหนาแน่นแบบเฉพาะที่สำหรับการประหยัดพลังงาน โดยที่มีจุดประสงค์เพื่อช่วยลดปริมาณจำนวนของสถานีตัวรับรู้ที่จำเป็นต้องเปิดทำงานรวมไปถึงความหนาแน่นของปริมาณการใช้ช่องสัญญาณวิทยุให้น้อยลงในขณะที่ยังสามารถคงสภาพพื้นที่ครอบคลุมการตรวจจับเดิมของระบบเอาไว้ได้ วิทยานิพนธ์นี้ได้แปลงปัญหาพื้นที่ครอบคลุมการตรวจจับไปเป็นปัญหาเซตครอบคลุมแบบถ่วงน้ำหนัก สถานีตัวรับรู้แต่ละตัวจะทำการคำนวณผลเฉลยตามหลักเชิงละโมบจากการแก้ปัญหาเซตครอบคลุมของตัวเอง ซึ่งผลเฉลยนี้จะบ่งชี้ถึงกลุ่มของสถานีตัวรับรู้จากในหมู่สถานีทั้งหมดที่มีตัวมันเองรวมกับสถานีเพื่อนบ้านของมันที่สมควรจะหลับไปเพื่อประหยัดพลังงาน อย่างไรก็ตามผลเฉลยที่ได้จากตัวสถานีตัวรับรู้เทียบกับผลที่ได้จากสถานีเพื่อนบ้านอาจไม่ตรงกัน ดังนั้นในวิทยานิพนธ์นี้ยังได้นำเสนอแผนการลงมติสำหรับการเลือกหลับสถานีตัวรับรู้เพื่อให้มั่นใจได้ว่าสถานีตัวรับรู้ที่ถูกเลือกนั้นเป็นสถานีตัวรับรู้ที่เหมาะสมที่สุดในอาณาบริเวณนั้นที่สมควรแก่การหลับโดยที่ไม่ทำการครอบคลุมพื้นที่ตรวจจับของระบบเดิมแย่ลง

Other Abstract (Other language abstract of ETD)

Wireless sensor networks consist of a large number of wireless sensor nodes with limited power and resource. To prolong network lifetime, the energy consumption must be somehow reduced. This work proposes a localized density control algorithm for energy savings. The goals are to maintain a minimal number of active sensor nodes and to reduce radio-traffic intensity while conserving the sensing coverage of the network. In this thesis, the sensing coverage problem is transformed into a weighted set-cover problem. Each node locally computes a greedy solution of such a problem. This localized greedy solution indicates candidate nodes among this node and its neighbors for sleeping. However, the solution of a node and those of its neighbors might be different. Therefore, this work also includes a voting scheme for selecting inactive nodes to assure that the selected nodes are the most deserving nodes in the area to sleep without worsening the sensing coverage.

Link to Full Text

Share

COinS