Local event boundary detection with unreliable sensors: Analysis of the majority vote scheme

详细信息    查看全文

• 作者：Peter Brass^a ; ^{peter@cs.ccny.cuny.edu" class="auth_mail" title="E-mail the corresponding author} ; Hyeon-Suk Na^b ; ^{hsnaa@ssu.ac.kr" class="auth_mail" title="E-mail the corresponding author} ; Chan-Su Shin^c ; ^{cssin@hufs.ac.kr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Boundary detection ; Unreliable sensor ; Majority vote scheme ; Computational geometry ; Algorithm
• 刊名：Theoretical Computer Science
• 出版年：2015
• 出版时间：23 November 2015
• 年：2015
• 卷：607
• 期：part_P1
• 页码：96-112
• 全文大小：657 K

文摘

In this paper we study the identification of an event region X within a larger region Y, in which the sensors are distributed by a Poisson process of density λ to detect this event region, i.e., its boundary. The model of sensor is a 0–1 sensor that decides whether it lies in X or not, and which might be incorrect with probability p. It also collects information on the 0–1 values of the neighbors within some distance r and revises its decision by the majority vote of these neighbors. In the most general setting, we analyze this simple majority vote scheme and derive some upper and lower bounds on the expected number of misclassified sensors. These bounds depend on several sensing parameters of p, r, and some geometric parameters of the event region X. By making some assumptions on the shape of X, we prove a significantly improved upper bound on the expected number of misclassified sensors; especially for convex regions with sufficiently round boundary, and we find that the majority vote scheme performs better in the simulation rather than its theoretical upper bound.