全網路的廣播應用非常廣泛，舉凡無線隨意網路之中路由的建立，無線感測網路之中程式碼的更新，甚至是近年來熱門的機器與機器、雲端機器人等，都可見到全網路的廣播應用。本論文探討的問題是如何有效率的從網路中一個來源節點，經由網路內的轉傳，將封包廣播給網路上的所有節點。近年來網路編碼已經在許多網路環境中被證實可有效的增進網路效能，本篇探討如何使用譜圖理論所得到的拓樸資訊來執行可調適的網路編碼，利用此分散式演算法，使得網路編碼的效能提升，減少廣播的次數、並降低全部群體完成廣播的執行時間，以有效節省能源並達到延長整體網路的運作時間。最後，本研究所提出的機制以及目前知名研究所提出的機制進行電腦模擬，模擬結果顯示本研究所提出的機制相較於知名研究所提出的機制有較少整體傳輸次數，並有效降低廣播完成的時間、降低整體網路能源消耗，以延長網路運作的時間。

Network-wide broadcast plays a crucial role in the success of many applications in wireless networks. For example, route establishment in wireless ad hoc network, code update for wireless sensor network and group broadcast in recently popular M2M (machine to machine) communication and cloud robotics all require the support of network-wide broadcast in order to function properly. On the other hand, recent research has shown that network coding is effective on improving the performance of wireless networks. In this study, we investigated the network-wide broadcast issue in an infrastructure-less wireless network. We proposed a novel network-wide broadcast algorithm which adopts network coding in conjunction with the spectral graph theory. The proposed scheme takes advantage of each node’s spectral property in a network, obtained in a distributed manner, in assisting on the determination of the best network coding length when each node performs forwarding by broadcast data to its neighbors. The proposed scheme is designed to minimize the total amount of packets transmitted by each node while significantly reducing the network-wide broadcast completion time. The proposed scheme and some well-known schemes in the literature have been implemented using NS2 simulator. A series of computer simulations have been conducted for the proposed scheme and the well-known schemes. The results have shown that the proposed scheme has significantly outperformed the well-known schemes in terms of the total amount of transmitted packets, the completion time of network-wide broadcast and the network operating lifetime.

[1] C. E. Perkins. Ed. “Ad Hoc Networking,” Addison-Wesley, 2001.
[2] C. Fragouli, J. Widmer, and J.-Y. L. Boudec, “Efficient broadcasting using network coding,” IEEE/ACM Transactions on Networking, vol.16, no.2, pp.450-463, Apr. 2008.
[3] C. Ho, K. Obraczka, G. Tsudik, and K. Viswanath. “Flooding for reliable multicast in multi-hop ad hoc networks,” In Proceedings of the International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communication (DIALM), pp. 64–71, 1999.
[4] D. A. Spielman. “Spectral Graph Theory and its Applications,” pp. 29-38, FOCS 2007.
[5] D. Fay, H. Haddadi, A. Thomason, R. Mortier, A. Jamakovic, S. Uhlig,M. Rio, “Weighted spectral distribution for internet topology analysis: theory and applications,” J. IEEE/ACM Trans. Networking (TON), Volume 18, Issue 1, Feb. 2010, 164–176.
[6] D. Katsaros, N. Dimokas, and L. Tassiulas, “Social Network Analysis Concepts in the Design of Wireless Ad Hoc Network Protocols,” Network, IEEE, vol. 24, pp. 23–29, Nov-Dec 2010.
[7] E. Royer and C.-K. Toh, “A Review of Current Routing Protocols for Ad Hoc Wireless Networks,” Personal Communications, IEEE, pp. 46–55. Apr. 1999.
[8] F.R.K. Chung, “Spectral Graph Theory,” Am. Math. Soc., 1997.
[9] G. Wu et al. “M2M: from mobile to embedded internet,” IEEE Communication Magazine, vol. 49, no. 4, Apr. 2011.
[10] G. Q. Hu, W. P. Tay, and Y. G. Wen, “Cloud robotics: Architecture, challenges and applications,” IEEE Network, Special Issue on Machine and Robotic Networking, vol. 26, no. 3, pp. 21–28, May-Jun. 2012.
[11] H. Lim and C. Kim. “Multicast tree construction and flooding in wireless ad hoc networks,” In Proceedings of the ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWIM), 2000.
[12] H. Y. Shwe and F. Adachi, “Power efficient adaptive network coding in wireless sensor networks,” in Communications (ICC), 2011 IEEE International Conference on, pp. 1 –5, Jun. 2011.
[13] I. H. Hou, Y. E. Tsai, T. Abdelzaher, and I. Gupta, “Adapcode: Adaptive network coding for code updates in wireless sensor networks,” INFOCOM 2008, Apr. 2008.
[14] J. Jetcheva, Y. Hu, D. Maltz, and D. Johnson. “A simple protocol for multicast and broadcast in mobile ad hoc networks,” Internet Draft: draft-ietf-manet-simple-mbcast-01.txt, Jul. 2001.
[15] J. Yick, B. Mukherjee, D. Ghosal, “Wireless sensor network survey,” Computer Networks, p.2292–2330, Dec. 2008.
[16] K. Wehmuth, A. Ziviani, “DACCER: Distributed Assessment of the Closeness Centrality Ranking in complex networks,” Computer Networks: The International Journal of Computer and Telecommunications Networking, vol.57, no.13, pp. 2536-2548, Sep. 2013.
[17] K. Wehmuth and A. Ziviani, “Distributed location of the critical nodes to network robustness based on spectral analysis,” in Proc. of the Latin American Network Operations and Management Symposium –LANOMS. IEEE, Oct. 2011.
[18] N. Wisitpongphan, O.K. Tonguz, J.S. Parikh, P. Mudalige, F. Bai, V. Sadekar. “Broadcast storm mitigation techniques in vehicular ad hoc wireless networks,” IEEE Wireless Communications, vol. 14, no. 6, pp. 84–94, Dec. 2007
[19] P. A. Chou, Y. Wu, and K. Jain, “Practical network coding,” in Proc.41st Annu. Allerton Conf. Communication, Control, and Computing, Monticello, IL, Oct. 2003.
[20] R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung, “Network information flow,” IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204–1216, Jul. 2000.
[21] Ralf Koetter , Muriel Médard, “An algebraic approach to network coding,” IEEE/ACM transactions on Networking (TON), v.11 n.5, p.782-795, Oct. 2003
[22] R. Bassoli, H. Marques, J. Rodriguez, K. Shum, and R. Tafazolli, ”Network coding theory: a survey,” IEEE Communications Surveys Tutorials, vol. 15, pp. 1950–1978, 2013.
[23] S. Ni, Y. Tseng, Y. Chen, and J. Sheu. “The broadcast storm problem in a mobile ad hoc network.” In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM), pp. 151–162, 1999.
[24] S.-Y. R. Li, R. W. Yeung, and N. Cai, “Linear network coding,” IEEE Trans. Inf. Theory, vol. 49, pp. 371–381, Feb. 2003.
[25] T. Matsuda, T. Noguchi, and T. Takine, “Survey of network coding and its applications,” IEICE Trans. Commun., vol. E94-B, no. 3, pp.698–717, Mar. 2011..
[26] T. Stathopoulos, J. Heidemann, D. Estrin, “A remote code update mechanism for wireless sensor networks,” UCLA GENS Technical Report # 30, 2003.