chapter  12
46 Pages

Adaptive Social Hierarchies: From Nature to Networks

Contents 12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 12.2 Social Hierarchies in Nature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

12.2.1 Formation and Maintenance of Hierarchies . . . . . . . . . . . . . . . . . . . . 308 12.2.2 Purpose of Social Hierarchies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310

12.3 Using Adaptive Social Hierarchies in Wireless Networks . . . . . . . . . . . . . . . 311 12.3.1 Constructing an Adaptive Social Hierarchy . . . . . . . . . . . . . . . . . . . . 313

12.4 Pairwise ASH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 12.4.1 Pairwise ASH with Reinforcement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321

12.5 One-Way ASH (1-ASH) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 12.5.1 Domination ASH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 12.5.2 Domination Ratio with Switching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327

12.6 Dealing with Mixed Mobility: An Agent-Based Approach. . . . . . . . . . . . . . 331 12.6.1 Agent Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 12.6.2 Realistic Meetings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334

12.7 Suitable Attributes to Rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 12.7.1 Energy/Lifetime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 12.7.2 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 12.7.3 Buffer Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 12.7.4 Functions of Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 12.7.5 Levels and Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339

12.8 Example Scenarios of ASH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 12.8.1 Enhancing Spray and Focus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 12.8.2 Enhanced Context-Aware Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 12.8.3 A Simple Cross-Layer Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342

12.8.3.1 Medium Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 12.8.3.2 Routing and Replication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 12.8.3.3 Application. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344

12.9 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 12.10 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345

12.10.1 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 12.10.2 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347

Social hierarchies are a common feature of the Animal Kingdom and control access to resources according to the fitness of the individual. We use a similar concept to form an adaptive social hierarchy (ASH) among nodes in a heterogeneous wireless network so that they can discover their role in terms of their base attributes (such as energy or connectivity). Three different methods of forming the hierarchy are presented (pairwise, one way, and agent based). With Agent ASH we show that the time taken for the hierarchy to converge decreases with increasing N , leading to good scalability. The ranked attributes are used as a network underlay to enhance the behavior of existing routing protocols. We also present an example of a cross-layer protocol using ranked connectivity and energy. The ASH provides an abstraction of real-world, absolute values onto a relative framework and thus leads to a simpler and more general protocol design.