ABSTRACT
CONTENTS 6.1 Preliminaries and Network Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
6.1.1 Ad Hoc Wireless Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 6.1.2 Opportunistic Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
6.2 Oblivious Routing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 6.2.1 Epidemic Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
6.2.1.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 6.2.1.2 Design Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 6.2.1.3 Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.2.2.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 6.2.2.2 Design Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 6.2.2.3 Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . 166
6.3 Encounter-Based Uni-cast Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 6.3.1 Encounter-Based Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
6.3.1.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 6.3.1.2 Encounter-Based Routing . . . . . . . . . . . . . . . . . . . . . . 167 6.3.1.3 Securing EBR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
6.3.2 Optimal Opportunistic Forwarding . . . . . . . . . . . . . . . . . . . . . . . . . 168 6.3.2.1 Preliminary and Motivation . . . . . . . . . . . . . . . . . . . . . 168 6.3.2.2 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
6.3.3 Energy-Efficient Opportunistic Forwarding . . . . . . . . . . . . . . . . . 170 6.3.3.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 6.3.3.2 Optimization Formulation . . . . . . . . . . . . . . . . . . . . . . 170
6.3.4 Policy Design and Optimal Policy . . . . . . . . . . . . . . . . . . . . . . . . . . 171 6.3.5 NUS Student Contact Trace Model . . . . . . . . . . . . . . . . . . . . . . . . . 171
6.3.5.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 6.3.5.2 Delay-Tolerant Networking . . . . . . . . . . . . . . . . . . . . . 172
6.3.6 Location-Based Routing (PER) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 6.3.6.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 6.3.6.2 TH-SMP Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 6.3.6.3 Contact Probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 6.3.6.4 Delivery Probability Metrics . . . . . . . . . . . . . . . . . . . . 174
6.3.7 Delegation Forwarding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 6.3.8 Encounter-Based Routing (RAPID) . . . . . . . . . . . . . . . . . . . . . . . . 175
6.3.8.1 Selection Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 6.3.8.2 Inference Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 6.3.8.3 Control Channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
6.4 Social-Based Uni-cast Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 6.4.1 Bubble Rap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
6.4.1.1 Community Detection . . . . . . . . . . . . . . . . . . . . . . . . . . 178 6.4.1.2 Bubble Forwarding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
6.4.2 Social Feature-Based Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 6.4.2.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 6.4.2.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 6.4.2.3 Feature Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 6.4.2.4 Routing Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
6.4.3 SimBet Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 6.4.3.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 6.4.3.2 Betweenness Centrality and Similarity . . . . . . . . . . 182 6.4.3.3 SimBet Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
6.4.4 Homing Spread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 6.4.4.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 6.4.4.2 Homing Spread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
6.4.5 SOSIM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
6.4.5.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 6.4.5.2 Forwarding Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 185 6.4.5.3 Social Similarity Metrics . . . . . . . . . . . . . . . . . . . . . . . 186
6.5 Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 6.5.1 Multicasting in Delay-Tolerant Networks . . . . . . . . . . . . . . . . . . . 187
6.5.1.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 6.5.1.2 Single-Data Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . 188 6.5.1.3 Multiple-Data Multicast . . . . . . . . . . . . . . . . . . . . . . . . 188
6.5.2 SCOOP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 6.5.2.1 Benefits of Two-Hop Relaying . . . . . . . . . . . . . . . . . . 190 6.5.2.2 Positively Correlated Paths . . . . . . . . . . . . . . . . . . . . . 190 6.5.2.3 Relaying Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
6.1 Preliminaries and Network Models 6.1.1 Ad Hoc Wireless Networks A wide range of novel applications have been enabled with the advance in inexpensive wireless network devices. Portable devices, such as cell phones and laptops, are equipped with wireless modules, which enable the access of information via Internet access points anywhere, anytime. A difficulty in the deployment of wireless networks is the need to have a large number of base stations that cover the whole network area. The energy consumption for data transmission of the battery-powered devices is also another challenge. These problems are addressed by ad hoc wireless networking through allowing mobile nodes to communicate directly with each other without the help of any communication infrastructure. Intermediate nodes between two nodes that are not in direct transmission range of each other can serve as voluntary routers to route messages.
