Brooks–Iyengar algorithm

The Brooks–Iyengar algorithm or Brooks–Iyengar hybrid algorithm ^[1] is a distributed algorithm, that improves both the precision and accuracy of the interval measurements taken by a distributed sensor network, even in the presence of faulty sensors.^[2] The sensor network does this by exchanging the measured value and accuracy value at every node with every other node. And it computes the accuracy range and a measured value for the whole network from all of the values collected. Even if some of the data from some of the sensors is faulty, the sensor network will not malfunction. The algorithm is fault-tolerant and distributed. It could also be used as a sensor fusion method. The precision and accuracy bound of this algorithm have been proved in 2016.^[3]

Background

The Brooks–Iyengar hybrid algorithm for distributed control in the presence of noisy data combines Byzantine agreement with sensor fusion. It bridges the gap between sensor fusion and Byzantine fault tolerance.^[4] This seminal algorithm unified these disparate fields for the first time. Essentially, it combines Dolev’s^[5] algorithm for approximate agreement with Mahaney and Schneider’s fast convergence algorithm (FCA). The algorithm assumes N processing elements (PEs), t of which are faulty and can behave maliciously. It takes as input either real values with inherent inaccuracy or noise (which can be unknown), or a real value with apriori defined uncertainty, or an interval. The output of the algorithm is a real value with an explicitly specified accuracy. The algorithm runs in O(NlogN) where N is the number of PEs: see Big O notation. It is possible to modify this algorithm to correspond to Crusader’s Convergence Algorithm (CCA),^[6] however, the bandwidth requirement will also increase. The algorithm has applications in distributed control, software reliability, High-performance computing, etc.^[7]

Algorithm

The Brooks–Iyengar algorithm is executed in every sensor node of a distributed sensor network. Each sensor exchanges their measured value and accuracy value with all other sensors in the network. The accuracy range the algorithm finds is the lowest lower bound and the highest upper bound returned from all the sensors. The "fused" measurement is a weighted average of the midpoints of the regions found.^[8] The concrete steps of Brooks-Iyengar algorithm are shown in this section. Each PE performs the estimation separately:

Input:

The measurement sent by PE k to PE i is a closed interval $[l_{k,i},h_{k,i}]$ , $1\leq k\leq N$

Output:

The output of PE i includes a point estimate and an interval estimate

PE i receives measurements from all the other PEs.
Divide the union of collected measurements into mutually exclusive intervals based on the number of measurements that intersect, which is known as the weight of the interval.
Remove intervals with weight less than $N-\tau$ , where $\tau$ is the number of faulty PEs
If there are L intervals left, let $A_{i}$ denote the set of the remaining intervals. We have $A_{i}=\{(I_{1}^{i},w_{1}^{i}),\dots ,(I_{L}^{i},w_{L}^{i})\}$ , where interval $I_{l}^{i}=[l_{I_{l}^{i}},h_{I_{l}^{i}}]$ and $w_{l}^{i}$ is the weight associated with interval $I_{l}^{i}$ . We also assume $h_{I_{l}^{i}}\leq h_{I_{l+1}^{i}}$ .
Calculate the point estimate $v_{i}'$ of PE i as $v_{i}'={\frac {\sum _{l}{\frac {(l_{I_{l}^{i}}+h_{I_{l}^{i}})\cdot w_{l}^{i}}{2}}}{\sum _{l}w_{l}^{i}}}$ and the interval estimate is $[l_{I_{1}^{i}},h_{I_{L}^{i}}]$

Example:

Consider an example of 5 PEs, in which PE 5 ( $S_{5}$ ) is sending wrong values to other PEs. The following Table is the values received by $S_{1}$ .

	$S_{1}$	$S_{2}$	$S_{3}$	$S_{4}$	$S_{5}$
$S_{1}$ values	$[2.7,6.7]$	$[0,3.2]$	$[1.5,4.5]$	$[0.8,2.8]$	$[1.4,4.6]$

We draw a Weighted Region Diagram (WRD) of these intervals, then we can determine $A_{1}$ for PE 1 according to the Algorithm:

$A_{1}=\{([1.5,2.7],4),([2.7,2.8],5),([2.8,3.2],4)\}$

which consists of intervals where at least 4(= $N-\tau$ = 5−1) measurements intersect. The output of PE 1 is equal to

${\frac {4*{\frac {1.5+2.7}{2}}+5*{\frac {2.7+2.8}{2}}+4*{\frac {2.8+3.2}{2}}}{13}}=2.625$

and the interval estimate is $[1.5,3.2]$

Algorithm characteristics

Faulty PEs tolerated < N/3
Maximum faulty PEs < 2N/3
Complexity = O(N log N)
Order of network bandwidth = O(N)
Convergence = 2t/N
Accuracy = limited by input
Iterates for precision = often
Precision over accuracy = no
Accuracy over precision = no

References

↑ Richard R. Brooks & S. Sithrama Iyengar (June 1996). "Robust Distributed Computing and Sensing Algorithm". Computer. IEEE. 29 (6): 53–60. doi:10.1109/2.507632. ISSN 0018-9162. Retrieved 2010-03-22.
↑ Mohammad Ilyas; Imad Mahgoub (July 28, 2004). Handbook of sensor networks: compact wireless and wired sensing systems (PDF). bit.csc.lsu.edu. CRC Press. pp. 25–4, 33–2 of 864. ISBN 978-0-8493-1968-6. Retrieved 2010-03-22.
↑ "On Precision Bound of Distributed Fault-Tolerant Sensor Fusion Algorithms". ACM Computing Surveys (CSUR). 49 (1, July 2016).
↑ D. Dolev (Jan 1982). "The Byzantine Generals Strike Again" (PDF). J. Algorithms. 3 (1): 14–30. doi:10.1016/0196-6774(82)90004-9. Retrieved 2010-03-22.
↑ L. Lamport; R. Shostak; M. Pease (July 1982). "The Byzantine Generals Problem". Transactions on Programming Languages and Systems. ACM. 4 (3): 382–401. doi:10.1145/357172.357176. Retrieved 2010-03-22.
↑ D. Dolev; et al. (July 1986). "Reaching Approximate Agreement in the Presence of Faults" (PDF). Journal of the ACM (JACM). ACM Press. 33 (3): 499–516. doi:10.1145/5925.5931. ISSN 0004-5411. Retrieved 2010-03-23.
↑ S. Mahaney & F. Schneider (1985). "Inexact Agreement: Accuracy, Precision, and Graceful Degradation". Proc. Fourth ACM Symp. Principles of Distributed Computing. ACM Press, New York,: 237–249. CiteSeerX 10.1.1.20.6337. |access-date= requires |url= (help)
↑ Sartaj Sahni and Xiaochun Xu (September 7, 2004). "Algorithms For Wireless Sensor Networks" (PDF). University of Florida, Gainesville. Retrieved 2010-03-23.

This article is issued from Wikipedia - version of the 11/18/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Brooks–Iyengar algorithm

Background

Algorithm

Algorithm characteristics

See also

References