Network Coded Flooding

Abstract

Prior work of network coding is mainly focusing on multicast traffic. In this thesis, we propose a new network coding based communication algorithm called Network Coded Flooding (NCF) which is related to network wide broadcast. This designed algorithm is an integration of network coding and one of the commonly used broadcasting techniques in wireless networks. In this thesis, we choose Probabilistic Flooding Algorithm (PFA) to integrate with network coding since it is a simple and robust flooding algorithm; it can be used in random wireless networks; it can work without any network topology information. As with PFA, NCF has a parameter of rebroadcast probability that controls packets’ rebroadcasts when receiving innovative packets. During the process of designing NCF, we also consider the issues how efficient network coding can achieve in a random wireless network even if the system process ability is low and available memory space is also limited. Therefore, the idea of generation is used and we also propose a specific generation management method in this thesis that is able to let system occupy little system memory space while good network performance (such as successful packet delivery, low packet delay and great energy savings) and relatively low system process complexity are guaranteed. NCF is a practical network coding based flooding algorithm that can be used in random wireless networks; that does not need any network topology information; that huge amount of data is allowed to be transmitted during the communication process; that the requirements of buffering and network process ability are at a relatively low level. We simulate such algorithm in Network Simulator 2 (NS2), and the simulation results show that NCF can realize the benefits in terms of reliability, working efficiency and energy saving if related parameters (such as generation size or maximum number of generations per node has ) of NCF are set accurately. In addition, reasonable trade-off schemes are also given through analyzing the obtained simulation results, which give general ideas about how to accurately use and change the related parameters of NCF in order to efficiently balance the relationship between network requirements and network performance.