Advanced Wireless Networks, 3rd Edition

2Adaptive Network Layer

2.1 Graphs and Routing Protocols

The most important function of the network layer is routing. A tool used in the design and analysis of routing protocols is graph theory. Networks can be represented by graphs where mobile nodes are vertices and communication links are edges. Routing protocols often use shortest path algorithms. In this section we provide a simple review of the most important principles in the field which provides a background to study the routing algorithms.

• Elementary Concepts: A graph G(V,E) is two sets of objects, vertices (or nodes), set V and edges, set E. A graph is represented with dots or circles (vertices) interconnected by lines (edges). The magnitude of graph G is characterized by the number of vertices |V| (called the order of G) and the number of edges |E|, size of G. The running time of algorithms is measured in terms of order and size.
• Directed Graph: An edge e ∈ E of a directed graph is represented as an ordered pair (u,v), where u, v ∈ V. Here u is the initial vertex and v is the terminal vertex. Also assume here that u ≠ v. An example with
  
  
  is shown in Figure 2.1.1.
• Undirected Graph: An edge e ∈ E of an undirected graph is represented as an unordered pair (u,v) = (v,u), where u, v ∈ V. Also assume that u ≠ v. An example ...