# Energy-Efficient Check-and-Spray Geocast Routing Protocol for Opportunistic Networks
## 3 Proposed EECSG Routing Protocol  
The proposed EECSG protocol (described in Algorithm 1) consists of the following steps:  
1. Acquiring the location information on-the-go. At this step, two tasks are involved in predicting the node movement. The first tasks consist of collecting the mobility traces, which deals with location sampling and node's location information maintenance. The second task consists of extracting the information relevant to a given message from the available movement history. The following sub-steps are involved:1. Location sampling: A node location may either be sampled periodically or triggered by an external event. In periodic sampling, the choice of the sampling interval presents a trade-off between accuracy and energy consumption in the sense that fine-grained intervals provide a more accurate movement history and higher energy consumption while larger intervals consume less energy, but may fail to record important locations. With an event-triggered approach, the location is sampled only when a node is encountered. While this approach records only the locations in which the encounter opportunities are available, some of the encounters may not be regular. As such, when using this technique, we have collected GPS traces at regular intervals and logged them into a file in order to analyze them and uncover some correlations on the number of visits between nodes to a given location. 2. Location information maintenance: This is taken care of as follows: the geographic area of the network is partitioned into a grid of square cells, where each cell is treated as a place (i.e., a collection of nearby locations in the network), and every node then maintains a list of its most visited places. It is worth noting that here, a location is obtained by using the Global Positioning System (GPS). After location sampling, the information that is relevant to a given message is extracted from the available movement history. 2. Defining the destination cast as well as determining whether the current position is located within it. This involves the following sub-steps: 1. Identifying the message endpoint: A message in OppNet is created along with the Endpoint Identifier (EID), which specifies its destination address. Unlike unicasting and multicasting, the naming approach in geocasting depends on the geographical location/area and the membership of the location. A location could be a point, polygon, grid, circle, to name a few. Besides, the membership of a node is subject to time and space. This is different in the case of uni-casting and multicasting, where the message destination is assigned to a node along with its EID. 2. Cast definition: In geocasting, the message destination is defined as a cast, i.e., a geographical area considered as the destination of the transmitted message. All network users residing within a defined geographical area is a potential recipient of a message, i.e., a user is a recipient if a message destination address corresponds with its current location. A cast can be defined as a point, circle, polygon, grid, to name a few, and a user defines the cast as a point of Polygon, and the casts are defined as a set of pairs of two-dimensional coordinates. The strategies that are often used to identify the position of a point inside or outside the polygon include Crossing test, Angle Summation test and Triangle test [12]. In this work, we make use of the Crossing test algorithm. 3. Membership check: A node is identified with a location. To be qualified as a recipient of a message, a node is checked to determined whether it is a member of a location i.e., belongs to a cast. Frequently visited places also known as Point of Interests (Pols) are locations of the nodes that are often visited. The nodes that are currently located in the Pols in the polygon are checked. 3. Computing a forwarding utility metric to quantify the routing contribution that can be made by the nodes encountered outside the destination cast.