Article Preview
TopIntroduction
Nowadays, there are many types of wireless networks such as mobile or cellular networks, wireless personal area networks, wireless local area networks, wireless metropolitan area networks, and wireless ad hoc networks or MANETs. A MANET is a wireless ad hoc network made up of radio nodes organized in a mesh topology. In particular, a MANET is a group of autonomous nodes that form a dynamic, multihop radio network in a decentralized way (Loo et al., 2012). MANETs are deployed mainly in emergency situations like battlefield and natural disasters (e.g., for detection of earthquakes and floods) as there is no need to deploy any infrastructure to make nodes to communicate with each other. Nodes themselves implement the network management in a cooperative fashion. Such cooperation requires detecting routes and forwarding data packets. In ad hoc mode, all nodes participate in both data processing and routing tasks. The network also relies on the multihop type of routing for the data transmission, since the destination node is often out of the radio-range of the source node, and some nodes can act as a router to forward data (Kanellopoulos, 2017). Routing in MANETs can be categorized as: (1) proactive or (2) reactive routing. In proactive (or on-demand) routing protocols, all nodes periodically exchange routing information to maintain a consistent, updated, and complete network view. Each node uses the exchanged information to calculate the costs towards all possible destinations. On the other hand, reactive (or table-driven) routing does not depend on periodic exchange of routing information or route calculation. When a route is required, the node must start a route discovery process. Routing protocols in MANETS can also be categorized as: topology-based; destination-based; neighbor selection-based; and partitioning-based (Kanellopoulos, 2017). MANETs can “self-heal”, automatically re-routing around a node that has lost power.
In multihop networks, two main problems exist related with hidden and exposed terminals (Loo et al., 2012). A primary problem occurs when two or more nodes simultaneously transmit to a common destination node. A secondary problem occurs when a node receiving a transmission intended for it, is interfered with by another transmission not intended for it. The IEEE 802.11 Distributed Coordination Function (DCF) is the most popular medium access control (MAC) mechanism for ad hoc networks (Bianchi, 2000). DCF uses the carrier sense multiple access with collision avoidance (CSMA/CA) scheme as a mechanism to deal with collisions. It tries to schedule transmissions in a fair and efficient manner. However, DCF increases the medium access delay in proportion to the load on the network. It has also many drawbacks such as high overhead, high jitter, and limited QoS capabilities (Vergados et al., 2012). Moreover, DCF suffers from the fairness problem, which is caused by the existence of hidden terminals and exacerbated by the adopted binary exponential backoff algorithm to resolve contention (Xu & Saadawi, 2001). To achieve fair and efficient scheduling of transmissions, one of the dominant solutions is the Time Division Multiple Access (TDMA) since it is a simple MAC scheme and can prolong the devices’ lifetime by allowing them to transmit only a portion of the time during the conversation. Therefore, several TDMA schedulers have been proposed (Sgora et al., 2015). In a TDMA system, time is divided into frames that consist of time slots. Frame length is the number of time slots in each frame. A time slot has a unit time required for a packet to be transmitted between adjacent nodes. When nodes are in close range, collisions may occur, and the use of TDMA requires proper scheduling such as to avoid collisions. The Broadcast Scheduling Problem (BSP) (or TDMA message scheduling problem) considers how to assign at least one transmission slot for all nodes, while ensuring collision avoidance. BSP is a NP-complete problem (Ephremides & Truong, 1990) and its solution aims at the following (Chen et al., 2006):
- •
To minimize the total frame length and/or increase the network capacity;
- •
To maximize the number of simultaneous transmissions from non-interfering nodes;
- •
To minimize the average packet delay.