廣播封包一直是在無線感測網路上的一個重要議題。無線感測網路在處理時間同步或是建立路由路徑時，廣播封包必須無遺失的傳送到所有節點上，否則可能會造成無線感測網路上的路徑建立的錯誤或是其他更嚴重的問題。在廣播封包時最常碰到的問題是封包遺失，由於種種原因，廣播封包可能在傳送的過程中漏失而導致廣播終止，要避免這種情形的最好方法是使用溢流式廣播(Flooding)。溢流式廣播可以使目的節點附近所有可接收節點都傳送封包來避免封包遺失，然而這種廣播方式對於只有有限電力的無線感測網路而言卻顯得浪費。在本篇論文中，我們提出一個新的廣播方法BOPP以及局部化的廣播方法BOPPLOCAL，此方法使用預估每一節點在網路中所收到封包的機率來對每個節點進行評分，並以貪婪選取的方式來決定此節點是否需要成為網路在廣播封包時的中繼節點。

Broadcast presents a special challenge for Wireless Sensor Networks (WSNs). In situations such as time synchronization and routing path establishment, broadcast messages must be carefully transmitted to all nodes, or the time stamp of each node might be confuse and cause routing fail. To prevent packet loss while broadcast, flooding is the most robust way that lets all the reachable nearby node to rebroadcast to prevent packet loss. However it is energy consuming to let every node rebroadcast in a sensor network. To solve this problem, we need to limit the number of message-relaying nodes in the network, thus reduces the energy required to broadcast a message. In this thesis, we present centralized and decentralized power-preserving broadcast protocols called BOPP and BOPPLOCAL that utilize packet reception reliability metrics. The reliability score is computed for every communication link in the network. BOPP and BOPPLOCAL then select a set of repeater nodes that most contributes to a broadcast. The selection process is repeated whenever the score distribution changes.

[1] I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, \Wireless sensor
networks: a survey," Computer Networks, vol. 38, no. 4, pp. 393{422, 2002.
[2] J. Al-Karaki and A. Kamal, \Routing techniques in wireless sensor networks:
a survey," Wireless Communications, IEEE [see also IEEE Personal Commu-
nications], vol. 11, no. 6, pp. 6{28, 2004.
[3] A. D. Wood and J. A. Stankovic, \Denial of service in sensor networks," Com-
puter, vol. 35, no. 10, pp. 54{62, 2002.
[4] A. Qayyum, L. Viennot, and A. Laouiti, \Multipoint relaying for
ood-
ing broadcast messages in mobile wireless networks," System Sciences, 2002.
HICSS. Proceedings of the 35th Annual Hawaii International Conference on,
pp. 3866{3875, 2002.
[5] B. Williams and T. Camp, \Comparison of broadcasting techniques for mobile
ad hoc networks," Proceedings of the 3rd ACM international symposium on
Mobile ad hoc networking & computing, pp. 194{205, 2002.
[6] C. Ho, K. Obraczka, G. Tsudik, and K. Viswanath, \Flooding for reliable mul-
ticast in multi-hop ad hoc networks," DIALM '99: Proceedings of the 3rd in-
ternational workshop on Discrete algorithms and methods for mobile computing
and communications, pp. 64{71, 1999.
[7] S. Ni, Y. Tseng, Y. Chen, and J. Sheu, \The broadcast storm problem in a mo-
bile ad hoc network," Proceedings of the 5th annual ACM/IEEE international
conference on Mobile computing and networking, pp. 151{162, 1999.
[8] S. Guha and S. Khuller, \Approximation algorithms for connected dominating
sets," European Symposium on Algorithms, pp. 179{193, 1996.
[9] J. Wu and H. Li, \On calculating connected dominating set for e cient routing
in ad hoc wireless networks," DIALM '99: Proceedings of the 3rd international
workshop on Discrete algorithms and methods for mobile computing and com-
munications, pp. 7{14, 1999.
[10] I. Stojmenovic, M. Seddigh, and J. Zunic, \Dominating sets and neighbor
elimination-based broadcasting algorithms in wireless networks," IEEE Trans.
Parallel Distrib. Syst., vol. 13, no. 1, pp. 14{25, 2002.
[11] M. Min, H. Du, X. Jia, X. Jia, C. X. Huang, S. C.-H. Huang, and W. Wu, \Im-
proving construction for connected dominating set with steiner tree in wireless
sensor networks," J. of Global Optimization, vol. 35, no. 1, pp. 111{119, 2006.
[12] C. Adjih, P. Jacquet, and L. Viennot, \Computing connected dominated sets
with multipoint relays," Ad Hoc and Sensor Wireless Networks, vol. 1, no. 1-2,
pp. 27{39, 2005.
[13] F. Ingelrest and D. Simplot-Ryl, \Maximizing the probability of delivery of
multipoint relay broadcast protocol in wireless ad hoc networks with a realistic
physical layer," Lecture Notes in Computer Science, vol. 4325, p. 143, 2006.
[14] H. Li, H. Yu, and A. Liu, \A tree based data collection scheme for wireless sensor
network," ICNICONSMCL '06: Proceedings of the International Conference on
Networking, International Conference on Systems and International Conference
on Mobile Communications and Learning Technologies (ICNICONSMCL'06),
p. 119, 2006.
[15] A. Perrig and J. D. Tygar, Secure Broadcast Communication: In Wired and
Wireless Networks. Oct 2002.
[16] A. Perrig, R. Szewczyk, J. Tygar, V. Wen, and D. Culler, \Spins: Security
protocols for sensor networks," Wireless Networks, vol. 8, no. 5, pp. 521{534,
2002.
[17] J. Zhao and R. Govindan, \Understanding packet delivery performance in dense
wireless sensor networks," Proceedings of the 1st international conference on
Embedded networked sensor systems, pp. 1{13, 2003.
[18] K. Srinivasan, P. Dutta, A. Tavakoli, and P. Levis, \Understanding the causes of
packet delivery success and failure in dense wireless sensor networks," Proceed-
ings of the 4th international conference on Embedded networked sensor systems,
pp. 419{420, 2006.
[19] J. Polastre, R. Szewczyk, and D. Culler, \Telos: enabling ultra-low power wire-
less research," Proceedings of the 4th international symposium on Information
processing in sensor networks, 2005.
[20] K. Srinivasan and P. Levis, \Rssi is under appreciated," Proceeding of EmNets
2006, Jan 2006.