## 1 Introduction  
In recently years, underwater sensor networks (UWSNs) [1; 2] have been increasingly used in applications such as environmental monitoring, gas deposit exploration and exploitation, oceanographic data collection, oil spill monitoring, real-time warship monitoring, and disaster prevention. Although in general UWSNs are closely related to Wireless Sensor Networks (WSNs), several studies [3; 4; 5; 6] have shown that many of the traditional techniques designed for WSNs are not applicable to UWSNs. It is the characteristics of the underwater channel--commonly regarded as one of the most difficult wireless communication channels--that make the design of efficient routing protocols for UWSNs a very challenging task [7]. Key issues with the underwater channel include high propagation latency due to the low speed of acoustic signals in water (typically 1500 m/s), severely limited available bandwidth, high noise, and high error rates. These issues lead to excessive data retransmissions, high energy consumption and low packet delivery ratios, which all contribute to the difficulties of designing an efficient and reliable routing protocol for UWSNs. Geographic information routing has been widely accepted as a preferred method for routing packets in UWSNs as it does not require establishing/keeping complete routes or transmitting routing messages [8]. Each node knows its own location and the geographic information of the destination node and consequently can forward data packets to a locally optimal next-hop node closest to the destination node. As a result, geographic routing protocols are reasonably simple and scalable to large UWSNs, however they also suffer from serious drawbacks such as sparse network density, void communication regions, and inaccurate positioning of nodes, which also lead to excessive retransmissions, high energy consumptions and low packet delivery ratios. Therefore, one particular design goal of geographic information routing protocols for UWSNs is to minimize power consumption, while achieving high packet delivery ratio. [PERSON] _et al._[9] proposed a new information theory technique--network coding--to tackle the issues of power consumption and packet delivery ratio in multicast applications. Ever since its inception, a substantial number of researchers [10; 11; 12] have studied the benefits of network coding in wireless networks. Network coding allows each relay node to first encode received packets before forwarding the encoded data, which essentially decreases the size of transferred data, reduces the energy consumption at nodes, and improves the network bandwidth utilization, all contributing to the extension of the network lifetime. Network coding is also a promising technique for reducing data retransmissions and energy consumptions and for improving packet delivery ratio and network lifetime in UWSNs [13]. Because underwater sensor nodes possess more computational capabilities than those in wireless networks and furthermore the broadcast nature of underwater acoustic channels renders multiple routes from a source to a destination, the multiple routes coupled with the exceptional computational powers of the sensor nodes provide ample opportunities to apply network coding to geographic information routing in UWSNs. Network coding can be illustrated by a well-known pattern shown in Figure 1, where two nodes A and C exchange data packets \(x_{1}\) and \(x_{2}\) via a relay node B. When node B receives packages \(x_{1}\) and \(x_{2}\) from nodes A and C respectively, it broadcasts \(x_{1}\oplus x_{2}\) (their binary XOR) to both nodes A and C. When node A receives \(x_{1}\oplus x_{2}\), it uses its knowledge of \(x_{1}\) to retrieve \(x_{2}\). In a similar spirit, when node C receives \(x_{1}\oplus x_{2}\), it uses its knowledge of \(x_{2}\) to retrieve \(x_{1}\).