Localization Enhanced Mobile Networks

Abstract

The interest in mobile ad-hoc networks (MANETs) and often more precisely vehicular ad-hoc networks (VANETs) is steadily growing with many new applications, and even anticipated support in the emerging 5G networks. Particularly in outdoor scenarios, there are different mechanisms to make the mobile nodes aware of their geographical location at all times. The location information can be utilized at different layers of the protocol stack to enhance communication services in the network. Specifically, geographical routing can facilitate route management with smaller overhead than the traditional proactive and reactive routing protocols. In order to achieve similar advantages for radio resource management (RRM) and multiple access protocols, the concept of virtual cells is devised to exploit fully distributed knowledge of node locations. The virtual cells define clusters of MANET nodes assuming a predefined set of geographically distributed anchor points. It enables fast response of the network to changes in the nodes spatial configuration. More importantly, the notion of geographical location can be generalized to other shared contexts which can be learned or otherwise acquired by the network nodes. The strategy of enhancing communication services by shared contexts is likely to be one of the key features in the beyond-5G networks.

1. Introduction

The support for mobility was a large step towards realizing the full potential of wireless networks. The mobility of nodes brings about two large concerns. It affects radio propagation conditions making the propagation channels between transmitters and receivers more volatile and less predictable. It also complicates the network management at higher layers of the protocol stack, since the network need to be aware about the present locations of all mobile nodes. The solutions to address these two concerns are fundamentally dependent whether there is a supporting infrastructure such as fixed base stations and access points, or whether the nodes can only communicate directly with each other. The former scenario was introduced with the first generations of cellular networks whereas the latter scenario appeared in MANETs. The emerging 5G networks are expected to provide support not only to individual mobile nodes, but newly also to MANETs. Alternative strategy to conventional networks comprising named nodes are the so-called data-centric networks which were also assumed for MANETs. In these networks, the nodes advertise and replicate named data, so the network routing is driven by the requests for given data rather than for given nodes.

Most MANETs are formed by interconnected manned or unmanned vehicles on the ground or in the air, so they are also referred to as VANETs. Many new applications are envisioned particularly for networks of unmanned aerial vehicles (UAVs) or drones, and other high altitude platforms (HAPs) such as balloons [1]. Another prominent example of MANETs are the upcoming networks of the low-Earth orbit (LEO) satellite networks where inter-satellite communications will be a critical component for delivering the envisioned broadband services and the global Earth coverage.

The radio propagation environment and the node mobility drive intermittent and often unpredictable connectivity between nodes in MANETs. The challenge is to define the corresponding mathematical models which are tractable as well as sufficiently accurate [2]. At minimum, the radio propagation models need to incorporate path-loss, random shadowing and multi-path shadowing can be approximated by a two-ray ground reflection model. The mobility models require much more sophisticated strategies to account for individual and group behaviors of nodes including responses to various events, terrain profile, physical laws and many other aspects [3]. The discrepancy between the measurements in real-world networks and the protocol performances predicted from simulations can be largely attributed to inaccurate or inappropriate mobility models.

The dynamic nature of MANETs necessitates development of bespoke protocols, since conventional protocols such as TCP/IP used in wired networks would be very inefficient or even unusable, mainly due to very large overhead. For instance, MANETs require frequent packet retransmissions, re-establishing network routes to maintain connected paths between nodes, session management to deal with dropped connections, and security provisioning against internal and external attacks. Moreover, the bandwidth and packet payload is often limited, and the nodes may have reduced computing, communication and storage capabilities. This calls for carefully designed protocols to optimize the resource, so it is not surprising that protocol suits in the commercial MANETs are often proprietary, possibly modified versions of the protocols from research literature. Practical implementation of protocols also faces many common issues of software development including hidden bugs which may be extremely difficult to discover.

At the physical layer, the node mobility creates fast fading channels which can be mitigated by various diversity signaling techniques including error-correction channel coding schemes, multicarrier modulations, and multiple antennas systems. In MANETs, the mobility is limited to a given geographical area, and the nodes participating in the network are usually known beforehand. This simplifies the protocols for mobility management in MANETs by allowing fixed node identifiers. On the other hand, MANETs are more vulnerable to security attacks than cellular networks. For example, there is no centralized authority in MANETs which can be trusted, and relatively short lifespan and small traffic volumes do not allow statistically significant intrusion detection.

The main strategy of the upcoming 5G networks is to unite telecommunication systems and provide unified and transparent access in different scenarios using different technologies. Hence, the 5G networks should provide support for MANETs as well. However, unlike (D2D) single-hop communication links in the long-term evolution (LTE) 4G networks, the MANET support in the 5G networks is likely to enable more flexible integration of mobile sub-networks within the cellular infrastructure with computing centers. Especially the VANETs of connected vehicles on the ground or in the air is a highly anticipated application supported in the 5G systems. However, some degree of autonomy required for MANETs or VANETs while exploiting the 5G infrastructure if or when it is available will make the orchestration of communication and computing resources in these networks extremely challenging. Exploiting the location information of mobile nodes could significantly reduce the complexities of network control and management in the envisioned 5G systems.

Several key network services which must be provided in mobile networks are discussed in Section 2. We describe mobility management, and introduce different types of context. Geographical location is shown to be a specific case of a shared context within telecommunication networks which can be utilized to enhance the network services. We also briefly outline localization services in the 4G and 5G networks, since these networks are expected to support MANETs in future. In Section 3, we review conventional and geographical routing strategies in mobile networks that have been studied extensively in literature. In contrast, geographical RRM and multiple access schemes received much less attention in the literature. A new concept of virtual cells for geographical protocols at the link layer providing a fast response with minimum overhead to varying MANET topology is presented in Section 4. The chapter is concluded in Section 5.

2. Network services in mobile networks

2.1 Mobility management

We review three concepts which are crucial for decentralized applications in MANETs: mobility management, network contexts, and localization services. In particular, the applications in MANETs need to be at least partially distributed including node localization. The distributed applications rely on and are greatly affected by the characteristics of inter-node connectivity such as time varying capacity of links. The end-to-end path stability and delay is also affected by the network traffic load with possible congestion effects, the number of hops and the number of alternative routes between the source and the sink. From computing perspective, the mobility management requires information about locations of clients and server instances, and maintaining states of sessions to provide robustness against disruptions. The applications offering suspend and resume functions are less common in highly dynamic MANETs. Provided that there is enough bandwidth and additional latency can be tolerated, off-loading applications into a cloud solves the computing constraints of nodes. Distributed clouds known as cloudlets which are more easily accessible by the network nodes were introduce to balance the requirements for bandwidth, latency and computing. The resource utilization is optimized by profiling applications, devices and network connectivity. The recent trend is to run synchronized identical instances of an application in the network nodes as well as in the cloud in order to optimize fine-grain off-loading in real-time [4]. The application can call micro-services to alleviate the latency for setting up and configuring full virtual machine instances while utilizing more efficiently the cloud resources.

In highly mobile environments such as in MANETs, the decentralized applications can be implemented as smart messages combining data and code [4]. The code manipulating data is executed as needed along the route as the message is passed among the nodes. This approach offers good scalability while executing the application within a desired context, for example, when the message reaches a node in a given location. Smart messages also solve the problem of migrating services among nodes as needed. In addition, akin to data-centric networks with named data chunks, it is possible to use smart messages with unique global names to be requested by the network nodes.

In the 5G networks, the nodes in MANETs can benefit from mobility management mechanisms including tracking area lists and NAS (non-access stratum) messages, provided that these nodes are governed directly or indirectly by the 5G network controllers. The interesting and open research question is how to manage the mobility in networks where some but not all nodes in a MANET are controlled by the 5G network. Another open research question is how to exploit predicted node trajectories to simplify the mobility management by inferring the future node positions.

2.2 Context in mobile networks

Context in telecommunication networks can have different meanings [5]. It can be related to some objective in delivering telecommunication services which is supported by directly observable or implied conditions. Typical characteristics describing the context in telecommunication networks are following:

• Context can be defined locally or globally, and it can be set, managed, synchronized, combined, and transferred.

• Context often varies in time, but context-based adaptation can go beyond simply adjusting a few parameters, for example, to improve efficiency and resilience of the network.

• Context usually describes more complex conditions in the network, and it can be defined for a single node, a group of nodes or all nodes in network.

• Context can be shared, and learned individually or cooperatively, or predicted from past observations.

Context sharing is illustrated in Figure 1 where either information about individual contexts is shared explicitly, or some shared network conditions are observed individually by different network entities. In some cases, revealing the context such as geographical location could cause privacy and security concerns, which may require defining and enforcing context sharing policies. A trivial example of the shared context is time synchronization of nodes in a network required, for example, to define time slots for multiple access protocol.

Figure 1.

Sharing the context among different network entities.

We can assume different types of contexts such as context defined for connectivity, devices, applications and networks including availability of different resources. Here, our focus is specifically on geographical location as the context which is naturally shared among the network nodes. Similarly to time context, the shared location context can be acquired with the aid of an external source such as global satellite navigation system (GNSS), or the nodes can cooperate to define their locations relative to each other. Moreover geographical locations can be defined in the same or multiple spatial frames with the corresponding points of origin. In addition, geographical location can be defined more loosely as a position belonging to some specified geographical area such as a base station cell, inside the building and similar. Such coarse-grained localization is often sufficient in many applications, for example, to make off-loading decisions.

2.3 Localization in mobile networks

The most straightforward for determining the absolute locations of nodes in a geographical area is to employ GNSS which is cost-affordable technology with ubiquitous coverage outdoors. Recently, a number of countries launched their own now fully operational GNSS including USA (GPS), GLONASS (Russia), Galileo (Europe), Compass (China), and IRNSS (India). Localization errors of GNSS can be improved by correcting errors due to atmospheric propagation effects, using overlay signals from other satellites, and using terrestrial augmentation systems. Another strategy particularly suitable for mobile nodes is to employ inertial navigation systems (INS) onboard the nodes to perform dead reckoning. The INS can be used as a fallback system when the GNSS signals are temporarily unavailable, for instance, in between the satellite measurements.

Localization techniques in mobile networks which are independent of external signals assume measurements of signal strength, time of light, time differences, angle of arrival and others [6]. However, the measurements are always noisy, so more sophisticated statistical signal processing such as Kalman filtering is usually necessary. The localization by inferring distances to several other nodes known as trilateration is probably the most common. There are also network assisted localization methods which will support mobile networks in future (5G) systems. For instance, the node may inquiry about the identifier of the base station, or it can identify some other suitable radio beacon nearby to determine its approximate location. The 4G/5G base stations can assist the GNSS localization in order to reduce the location acquisition time. The 4G/5G standard also defines several references signals to assist the mobile nodes in measuring signal strength and observed difference in time of arrival for determining their location.

The positioning methods defined in the latest LTE standard adopted as the New-Radio (NR) 5G system are intended to provide a broad compatibility with other radio access technologies and exploit different measurements, especially in the uplink. The LTE positioning protocol (LPP) can assist the mobile nodes in determining their location using the control plane or user plane signaling. For instance, the base station can calculate the position using the GNSS measurements reported by the node, or the base station can provide the current satellite data to the node to facilitate its GNSS positioning. However, in situations when the GNSS signal is not be available, the preferred localization method in the 4G networks is based on the observed time difference of arrival (OTDOA) at the node from two or more base stations. The timing advance information which is used to synchronize multiple base station cells can be used for node localization. The locations of base stations are exactly known, so they can be utilized as anchors in conventional wireless localization techniques. There are also specifically defined positioning reference signals for signal timing and strength measurements, and the radio-frequency signature inference in the LTE. The open research question is how to provide network assisted localization services for MANETs where only some nodes are controlled by the 5G network.

3. Routing in mobile networks

3.1 Conventional routing protocols

Routing is a primary function of the network layer. The routing strategy is one of the key factors affecting the achievable QoS in the network. It is usually a compromise between fairness and traffic prioritization. The routing protocols need to define services for route creation, maintenance, updates, release and deletion, and it can also provide backup path to a faster recovery from link failures. The routing protocols in MANETs are fully distributed, and need to support mobility and the dynamic network topology, so they are often some variation of adaptive distance vector routing. The lifespan of links and routes in MANETs is dependent on the node mobility. The routing algorithm needs to be robust in order to improve the network stability despite existence of short-lived links. The local coordination among nodes is necessary to create longer-lived routes. The neighboring nodes periodically and iteratively share their knowledge of the dynamic network topology. The neighboring nodes are commonly discovered by sending hello and echo messages, for instance, using selective or controlled flooding. A simple flooding suffers from packet duplication to the point of packet implosion due to routes overlap. A straightforward improvement of flooding known as gossiping assumes a random walk to forward packets to the randomly selected outgoing links, but it cannot guarantee that all packets will reach all destinations. However, any routing protocols based on flooding do not scale well with the network size, if the network topology remains flat.

Apart from flooding, other basic mechanisms for route discovery assume next hop routing, and source based routing. The hello messages are also used to probe existing connections, if there were no other packets sent within a given time period to ensure that the neighboring nodes are still available.

The fundamental requirement for routing protocols is to discover optimum or near optimum routes which are loop-free. The loop-free routing is related to count-to-infinity problem which can occur if one of the intermediate routers goes down, or the routing updates between two or more nodes appear at the same time. The routing path optimality can be measured as end-to-end latency and bandwidth which can be approximated by the number of hops, or geographical distances. In many scenarios, the optimum routing is constrained by availability and fair use of resources. Although QoS-aware routing in MANETs is less common, the energy-aware routing algorithms are frequently assumed to avoid exhausting the battery life of the nodes serving as routers for all the other nodes. This can be achieved by periodically changing the group of nodes assigned to act as routers. The energy dissipation in nodes is greatly affected by the uniformity of traffic in the network. The battery life can be also extended by defining duty cycles with sleep modes and periodic awakening.

The routing is often combined with scheduling which can be reservation based to avoid collisions, or contention based scheduling is more efficient with smaller network traffic loads. The routing defines a particular network topology such as a chain topology which is useful for data aggregation, and cycle-free spanning tree for packet broadcasting and multicasting. Determining spanning tree is, however, problematic in dynamic networks where it is usually approximated, for example, using a reverse-path forwarding mechanism. The spanning tree topology can be also established at the level of multicast groups, and there can be multiple spanning trees from the same source to different multicast groups.

The data aggregation creates ever larger payload as the packet traverse along the route in exchange of reducing the number of packets to be sent. The overhead of routing protocols increases substantially with the network size and its dynamics. The updates via control messages consume the bandwidth and energy. The frequency of updates determines the temporal resolution, i.e., the maximum dynamics of network which can be supported. It is also possible to limit the spatial resolution of updates by constraining how far they can propagate in the network. This issues are more problematic for flat peer-to-peer MANETs, so creating a two-tier hierarchy of nodes by assigning nodes to clusters is usually desirable. The clusters are created by clustering algorithms, and each cluster elects a cluster head to forward packets to other clusters whereas the nodes in the cluster can communicate directly. The clustering of network reduces the number of hops to destination which reduces the end-to-end delay. The geographical distances between clusters can be measured by assuming the cluster centroids.

In general, different routing protocols are required for different scenarios and applications. The basic classification of routing protocols whether they provide route discovery on demand or a priori. These two classes are referred to as reactive and proactive protocols, respectively. Reactive protocols start the route discovery only when it is needed, i.e., there are data to be transported over the network. The process is initiated by the source with the data which avoids the need for routing tables in intermediate nodes and their periodic updates. However, the routing overhead and the packet payload increases with the number of hops as the route grows towards the destination, and each intermediate node appends its identifier to the packet header. However, the large packet size can create problems for the link layer protocol as it normally sends packets of predefined length, and larger packets must be sliced into multiple pieces. The route discovery is supported by broadcasting RREQ (route request) and receiving RREP (route reply) messages.

The discovered routes can be cached to improve efficiency and reduce the control overhead. However, the cached routing information eventually becomes stale. In addition, sudden changes to the route such as broken links are not detected. The on-demand routing strategy is more efficient for less frequent data transfers, and when the network topology is less dynamic, even though there is some delay before the route is set up. The reactive protocols are usually based on distance vector routing. The most well-known examples of reactive routing protocols in MANETs are AODV, DSR, and TORA [7]. For instance, the DSR protocol is useful for unicast traffic with multiple routes between source and destination, but it suffers from the growing packet size. The AODV protocol has constant packet sizes by keeping routing information in routing tables at intermittent nodes. Each route is assigned an expiry time, and only the routes in use are maintained. In addition, the sequence numbers in packets are used to keep track of active routes. The AODV protocol also supports multicast routing.

Next-hop routing protocols optimize only the following hop unlike the source based routing which considers the whole end-to-end path to the destination. The reactive protocols can update the route if the detected changes are above a certain threshold in order to reduce the frequent route updates in time-sensitive applications. The TEEN protocol is an example of this approach. The diffusion routing protocols propagate data along the reverse path of the initial query. Each path is associated with a gradient which is formed by propagating the initial data query or so-called the interest message. The data-query based routing protocols are unsurprisingly used in data-centric networks. The SPIN protocol is one example of these kinds of protocols.

Alternative strategy to reactive protocols is to assume proactive protocols which establish routes a priori, even if there are no data to be sent. This routing strategy is more suited to networks which larger traffic loads, but smaller mobility compared to reactive protocols. The proactive protocols can assume both distance vector and link state routing algorithms, and since they primarily rely on routing tables. The routing protocols can afford to search for the shortest path or the least cost route, and exploit multiple routes between the source and destination. The timers as well as sequence numbers are again utilized to detect stale routes and remove them from routing tables. The main disadvantage is periodic dissemination of routing information to maintain the routing tables.

The LEACH protocol is a popular example of proactive protocol used with topology clustering. The PEGASIS protocol improves the LEACH protocol, and uses sequential data aggregation over chain topology, although parallel aggregation strategies were also considered. Both these protocols are much more efficient for broadcasting than flooding based algorithms, since they assume topology clustering, however, their support for mobility is limited, and there are no considerations for QoS provisioning. Other examples of proactive protocols include OLSR, DSDV and WRP.

There are also hybrid routing protocols combing reactive and proactive protocols to maximize the benefits of both, for example, GRP and ZRP protocols.

3.2 Geographical routing protocols

Unlike previously described topology-based routing protocols, the geographical protocols derive their routing strategy from knowledge of geographical locations of other nodes in the network [7, 8, 9, 10, 11, 12]. The geographical locations can be also used to forecast the propagation conditions either by simple mathematical models if it needs to be performed in real time or by simulations if the off-line channel modeling is acceptable. Geographical locations can also represent the network node addresses, but this is less practical in mobile networks. There is also a concept of so-called virtual embeddings which assign the nodes with virtual stationary points serving as their addresses in order to alleviate the need for determining the actual geographical positions of each node.

The key idea of geographical routing which goes back to 1980 is to forward packets closer to the destination without prior path discovery, similarly to reactive routing protocols. Hence, geographical routing is particularly useful for MANETs with frequent topology changes, provided that the geographical locations of the neighboring nodes can be tracked. The common challenges of geographical routing protocols are difficulty in obtaining geographical locations of other nodes apart from the immediate neighbors, and accuracy and timeliness of determining the locations. Another issues is timeliness of location information as the nodes in MANETs are constantly moving, and before the relevant information is forwarded to other nodes, it may be obsolete. The performance of these protocols can be improved by predicting node locations knowing their mobility patterns which can be then used to predict the quality of links. It should be also noted that these protocols were primarily developed for 2D locations. The extension to 3D space including the airborne nodes may not be straightforward.

There are two basic strategies employed in geographical routing protocols. The first strategy is the one-hop greedy forwarding. The idea is to bring packet closer to the destination. As illustrative example in Figure 2, the source is connected to four nodes A, B, C, and D within its transmission radius. The node A is selected as the nearest node providing a forwarding progress towards the destination. The node B offers the best forwarding progress towards the destination among all the nodes connected with the source. The node C is selected as the one being closest to the azimuth towards the destination, so this strategy is referred to as compass routing. Finally, selecting the node D as the one being closest to the destination corresponds to a basic greedy strategy. More importantly, neither compass routing nor the nearest node with forwarding progress guarantees the loop free routing. The greedy forwarding can lead to a dead-end once there are no other nodes closer to the destination.

Figure 2.

Greedy one-hop forwarding and face routing in geographical routing protocols.

The second strategy is known as face routing. The faces are polygons depicted in blue and red color lines in Figure 2, and correspond to the node connections. The two red paths in Figure 2 are the face routes which are passing through nodes closest to but never crossing the line connecting the source and the destination. In order to guarantee the loops-free paths, it is common to combine both of these basic strategies. For instance, a well-known GPSR protocol combines greedy forwarding with face routing.

It should be noted all the geographical routing protocols described in Figure 2 assume unicast traffic, however, it is straightforward to extend these protocols for directional flooding. Similarly to multicast, geocast sends packets to a target group of nodes located in a given geographical area. There are also many geographical routing protocols for connected vehicles which exploit packet caching geographical maps of cities to predict the vehicle movements, for instance, GSR, GPCR, A-STAR, COIN, BREADCOMM, UMB and many others.

The location-aided routing (LAR) algorithm facilitates the geographical routing by partitioning the geographical area into two zones [8]. The expected zone narrows down the expected location of the destination. Such zone can be predicted from the past locations of the destination and information about the nodes mobility. The request zone defines the area where the search for a new route should be confined, for example, to flood the route request packet in order to significantly reduce the number of route-finding messages. If the packet is forward to a node outside the request zone, the packet is discarded. The LAR protocol can be combined with the greedy forwarding or directional flooding.

Geographical forwarding with expected zones is combined in the DREAM routing protocol. This protocol utilizes a position database where each entry contains a time-stamped information about the node current location, speed and direction in order to enable dead-reckoning predictions of location. The GRID routing protocol partitions the geographical area into a regular grid. At the local level, the packet routing is performed by some proactive routing algorithm whereas location-based routing is used to forward packets between the fields. The so-called home zone concept enforces all nodes within the home zone to keep information about the nodes belonging to that home zone, but which are temporarily away. In data centric networks, geographic location can be hashed to provide a unique key for data naming which also scales well in large networks.

4. Geographical RRM

Geographical RRM and multiple access schemes did not receive comparable attention as the geographical routing. Here, we partition the geographical region into non-overlapping areas referred to as virtual cells [13]. Unlike a partitioning into regular grid as for the GRID routing protocol discussed in the previous section, we define partitioning by the set of a priori chosen anchor points and partitioning is then form by the corresponding Voronoi regions. The virtual cells can be treated as the base station cells in cellular networks. It is then possible to pre-assign these cells with communication channels and other radio resources to facilitate distributed RRM and limit the exchange of control messages as well as to assume various channel reuse schemes. It is not necessary that the anchor points are static, or countably finite. The node clusters in MANET does not have to be fully contained within the virtual cells, although the virtual cells can be exploited to simply the clustering. In general, the utilization of virtual cells for RRM and multiple access is strongly dependent on the nodes mobility.

The RRM in wireless networks includes allocating communication channels, and setting the transmitting powers and data rates in order to use the limited radio resources as efficiently as possible. Unlike the cellular networks with centralized base station controllers, the RRM in MANETs is fully distributed, so the network nodes have to exchange enough information to coordinate multiple access, create network topology, manage interference, and determine routing. The scalability of MANETs is often achieved by a two-tier topology with clusters controlled by their respective cluster-heads. The nodes communicate with their cluster head who provide the centralized RRM within the cluster, however, the allocation of radio resources among the clusters remains distributed.

Virtualization of radio resources has recently emerged as a new paradigm to provide flexibility in efficiently sharing the network physical infrastructure. For instance, the network physical resources can be aggregated into a cloud, and then optimally partitioned to match the current demands of different users. It enables to define network function virtualization (NFV), virtual radio access networks (V-RAN), virtual operators and so on. Virtualization is expected to be the key design feature in the upcoming 5G networks. On the other hand, virtualization of the distributed radio resources in infrastructure-less networks is less straightforward, and it was rarely considered previously.

4.1 Virtual cells

The mobility model determines the optimum location of anchor points. Let the nodes in MANET follow the reference point group mobility (RPGM) model [14]. Such mobility consists of deterministic and random components. We assume that the random component represents a random waypoint (RWP) mobility, and for simplicity, the deterministic component representing a shared drift is the same for all nodes. For this mobility model, we can show that the optimum distribution of anchor points creates a hexagonal grid of equal-sized cells which is well known in the homogenous cellular networks. More precisely, the spatial mean of the RWP mobility is zero, i.e., such a node, on average, stays in one place. The optimum anchor point distribution is then given by the deterministic component of mobility, is also dependent on the initial placement of the network nodes. A large number of anchor points yield smaller virtual cells and more frequent handovers between them as the nodes move around. On the other hand, the virtual cells with large area may contain too many nodes, so the benefits of separating nodes into virtual cells diminish.

Assuming the deterministic component of the mobility is constant and the same for all nodes, and the random component of mobility for all nodes follows the same RWP model, the optimum anchor points lie on a rectangular grid with the dimensions √3R/2 and 3R/2, respectively, where R > 0 is a scaling factor. The scaling factor is set to match the RWP model, i.e., the variance of the random mobility component in order to evenly distribute the nodes among the virtual cells. The anchor grid is rotated, so that it is aligned with the mean direction of the mobility. The corresponding anchor points are located in the 2D positions,

$$a_{m,n}=\left[\mathit{Rm}{mod}_2\left(n-1\right),\mathrm{n}\surd \mathit{\text{3R}}/2\right]$$E1

where m and n are integers. The virtual cells are defined by the Voronoi regions corresponding to the anchor points, and R represents the virtual cell radius. The list of anchor points is communicated to every network node. The nodes can determine in which virtual cell they are presently located by finding the closest anchor point. The virtual cells can be further sectored to aid the RRM.

4.2 Transmission channel allocation

The radio propagation model adopted greatly affects the performance of the network protocols. For our purposes to illustrate the concept of virtual cells, we assume that every node is equipped with an omnidirectional antenna. The transmitted signals are attenuated by independently and identically distributed fading coefficients drawn from the Rayleigh distribution. In addition, the signals are attenuated by the free-space path-loss modeled as,

$$\mathrm{PL}\left(d\right)={\mathrm{PL}}_0\times d^{-\mathrm{u}}$$E2

where d is the distance from the transmitter antenna, and u > 1 is the path-loss coefficient. The attenuation factor PL₀ = λ_c/(4π) and λ_c denotes the carrier wavelength. The nodes are capable of full duplex transmissions, and they can transmit and receive at different frequency channels simultaneously.

As in the legacy cellular networks, the frequency channels can be reused in different virtual cells to increase the overall network capacity. The reuse distance for the hexagonal virtual cells defined by the anchor locations (1) is calculated as,

$$d_{\text{reuse}}=R\surd \left({\mathit{\text{3N}}}_{\mathit{cl}}\right)$$E3

where N_cl = (u² + v² + uv) is the number of cells in the cell cluster, and u and v are the number of cells which are crossed in order to arrive to the nearest co-channel cell within the hexagonal grid. Typical values of N_cl are 1, 3, 4, 7, and 9. In general, the larger the ratio d_reuse/R, the better the isolation between reused frequency channels, and the smaller the co-channel interference.

The cell coverage of the legacy cells and the proposed virtual cells are compared in Figure 3. In the former, the base station is at the cell center, so the cell radius R and the base station transmission range r are equal. In the latter, the transmission range r of the node at the virtual cell edge would have to be at least r > 2R in order to cover the whole area of the virtual cell.

Figure 3.

The legacy cell coverage (left), and the virtual cell coverage (right). The square node represents the anchor point of the virtual cell.

In order to assign the transmission channels, we assume there are F orthogonal frequency channels defined within the total bandwidth allocated to the network. Let F/N_cl be an integer, so the channels can be divided equally among the virtual cells in the same cell cluster. In order to provide the frequency diversity, the transmissions adopt a frequency hopping patterns, so each node selects a different frequency channel for transmission at every time slot. The co-channel interference within the virtual cell is mitigated by defining a set of orthogonal frequency hopping patterns for the nodes in that cell. Note that these hopping patterns are only orthogonal as long as all transmissions are time-slot synchronized. Since the neighboring cells within the same cell cluster may not be time synchronized, we can reduce the resulting co-channel interference by requiring that every frequency channel is used within the cell cluster only once every X > 0 consecutive time slots. In particular, assuming X = 3, the channel allocation matrix F is resilient against the time-slot misalignment of the neighboring transmissions by up to one time slot. The following Matlab code generates the orthogonal channel allocation matrix F of X × N_cl frequency tones over T consecutive time slots for N_cl cells in the cell cluster. The resilience of the channel allocation matrix F will be shown numerically in the subsequent section.

The following Matlab code is used to generate the frequency hopping matrix F with the parameters X, N_cl, and T. The function randint (K) generates a random integer between 1 and K.

NA = zeros(X*Ncl,T); % auxiliary matrix

FF = zeros(Ncl,T); % channel matrix

for u = 1:Ncl

for t = 1:T

i = find(NA(:,t)==0);

j = randint(length(i));

FF(u,t) = i(j);

NA(i(j),t) = 1;

if t==T, t1 = 1; else t1 = t + 1; end

NA(i(j),t1) = 1;

if t==1, t1 = T; else t1 = t-1; end

NA(i(j),t1) = 1;

end

end

4.3 Geographical multiple access

Many general multiple access (MAC) link layer protocols were developed for MANETs such as Z-MAC, reservation MAC, distributed MAC, and spatial correlations based MAC. These protocols usually assume synchronized time-slots and carrier sensing to mitigate packet collisions. Here, we only consider a simple MAC scheme which can be supported by the virtual cells. We assume a two-tier network topology where the nodes are grouped in node clusters, so the packets are routed within and among the clusters. Each cluster elects a single cluster head node. The nodes connected to more than one cluster head serve as the gateway nodes between those clusters. The nodes can play other roles such as relaying the packets for other nodes as well as they can originate and consume traffic. We assume that each virtual cell is assigned a single frequency channel or a set of frequency hopping patterns. The node transmissions follow these rules:

1. The nodes in a given virtual cell can transmit only using the frequency channel or the frequency hopping pattern assigned to that cell. However, the nodes can listen to transmissions at multiple frequencies assigned to other neighboring cells.

2. The nodes within a given virtual cell use TDMA or mutually orthogonal frequency hopping patterns.

3. The nodes in different cells of the virtual cell cluster use FDMA or the assigned frequency hopping patterns.

In general, it is important to distinguish between the node clusters defined among the network nodes, and the cell clusters defined for the frequency channel reuse among the virtual cells. Consequently, the network clusters can be created independently of the nodes locations within the virtual cells. The virtual cells can contain nodes belonging to different node clusters, or there may be no cluster head within the virtual cell to time-synchronize the nodes and make their transmissions orthogonal. In order to overcome these issues and form the node clusters within the virtual cells, we assume the following assignment of the roles for nodes within the virtual cells:

1. The nodes located within the same virtual cell form a single cluster.

2. The node closest to the anchor point (i.e., the virtual cell center) becomes the cluster head.

3. The nodes at the edge between the virtual cells assume the roles of the gateway nodes for the other nodes in the cluster.

Choosing the cluster head close to the cell center leads to more efficient coverage of the cell, and smaller transmission distances from the other less centered nodes. The gateway nodes are selected to be close to the cell edge, and at the same time, they should be in different angular sectors. Since the packet relaying increases the number of transmissions in the cell, it should be limited. The role assignment for the nodes can be done by modifying the existing protocols used for creating the node clusters. Additional splitting of the virtual cells can be used to selectively poll the nodes in a predetermined order, for instance, the polling message requests the response from the nodes in a given cell sector. The node roles should be periodically updated as they move around. The node handover when leaving one cell and joining another cell can be performed by contacting the cluster head in the new cell and requesting the allocation of radio resources in that cell. The RRM performed by the cluster heads can be aided by exchanging location information of nodes in the same virtual cell.

4.4 Numerical examples

We assume that the anchor points are regularly distributed according to Eq. (1), and the cell radius R = 500 m. There are N = 200 nodes initially uniformly distributed in the observation rectangular area of 2500 × 2500 m. The deterministic component of the node movements is exactly horizontal whereas the random mobility component assumes the RWM model. As the nodes move around in the Eastern direction, their roles reestablished every 10 time slots. There is exactly one cluster head and up to three gateway nodes in each virtual cell. The gateways are the nodes furthest away from the cell center in each of the three sectors: 30 to 150°, 150 to 270°, and −90 to 30°, respectively. Hence, it is possible that, in some virtual cells, the cluster-head also acts as a gateway to transmit packets to the neighboring cells, otherwise, the cluster-head transmits packets to the nodes within the same cell. The remaining nodes in the virtual cells only retransmit packets to the other nodes within the same cell. The pairs of transmitting and receiving nodes in the virtual cells are chosen at random with a uniform probability. The pairs are selected independently from one time slot to another as well as independently among different cells. Thus, all transmissions within the same cell are orthogonal unlike the simultaneous transmissions in different cells. Furthermore, the transmissions assume frequency hopping where every cluster of the virtual cells is assigned a distinctive set of mutually orthogonal frequency hopping patterns. These patterns are generated by the algorithm presented in the previous section. Even though the transmissions in each cell at every time slot are orthogonal, the co-channel interference can still appear due to a lack of time-slot synchronization among the virtual cells, even within the same cell cluster. We assume the virtual cell clusters with N_cl = 7 and N_cl = 3 cells equal to the respective frequency reuse factors. The simulation snapshots for these two cases are shown in Figure 4A and 4B, respectively. The arrows in these figures indicate randomly chosen transmissions. There are either one or two orthogonal transmissions per cell in each time slot.

Figure 4.

(A) A snapshot of transmissions in the 7-cell cluster network. (B) A snapshot of transmissions in the 3-cell cluster network.

We compare the following four transmission schemes. The first scheme, denoted as FR = 7/2 × 7, uses 2 × 7 = 14 distinct and orthogonal frequency channels with two of these channels allocated to every cell in the cluster of N_cl = 7 cells. Hence, there can be up to two simultaneous orthogonal transmissions in each cell in any given time slot. The frequency hopping pattern is created by randomly selecting two of the allocated frequency channels during each time slot. The second scheme, denoted as FR = 7/1 × 7, assumes seven orthogonal frequency hopping patterns over 3 × N_cl = 21 frequencies; one such pattern is allocated to each cell in the cell cluster. An example of these orthogonal patterns generated by the algorithm given in the previous section is presented in Table 1.

Cell	Frequency channels
1	20	17	5	19	7	4	19	21	9	6
2	18	10	8	11	5	18	5	13	17	14
3	4	16	2	16	10	20	17	20	1	2
4	11	12	15	1	13	8	12	15	4	3
5	19	1	21	14	21	9	1	11	7	15
6	5	3	18	3	6	15	14	6	12	8
7	9	14	4	17	12	3	10	16	10	13

Table 1.

A sample orthogonal allocation of 21 frequency channels to a cluster of 7 cells over 10 time-slots.

The third scheme, denoted as FR = 3/2 × 3, uses 2 × 3 = 6 distinct and orthogonal frequency channels the same way as the first scheme, but assuming only N_cl = 3 cells in the cell cluster. The fourth scheme, denoted as FR = 3/1 × 3, assumes three orthogonal frequency hopping patterns over 3 × N_cl = 9 frequencies which are generated and used the same way as in the second scheme.

The simulations in Matlab were performed to investigate the importance of time synchronization on the level of co-channel interference measured as the average signal-to-interference-plus-noise ratio (ASINR). The results for T = 100 time slots are shown in Figure 5 assuming that the transmissions at the neighboring cells can be misaligned by up to one time-slot corresponding to ∆T = 100%. More specifically, given the value ∆T, the transmissions in (N_cl − 1) neighboring cells are delayed by a fixed but randomly chosen time from the interval (0, ∆T). We observe that the frequency hopping patterns generated by the presented algorithm are constrained such that the time delays by up to one time slot do not create any additional co-channel interference. On the other hand, the schemes 7/2 × 7 and 3/2 × 3 generate additional co-channel interference if the transmissions at subsequent time slots at the neighboring cells are occurring at the same frequency.

Figure 5.

The average SINR versus the timing difference ∆T for 4 channel allocation schemes.

4.5 Discussion

The localization methods including GNSSS consume additional energy, however, these methods are now routinely used in MANETs operating in the outdoor environments. The geographical partitioning of the area using a set of predetermined locations referred to as anchor points and the corresponding Voronoi regions can facilitate the frequency, or more generally, transmission channel planning. The reuse and assignment of communication channels in the cells is one of the main tasks of the base station controllers in the legacy cellular networks. Here, this task is accomplished without any supporting physical infrastructure, so the MANETs can take advantage of the virtually defined cells. The infrastructure-less virtual cells should be contrasted with the NFV and other virtualization strategies which are used to pool and partition the shared radio resources in radio access networks.

We illustrated the key concept of virtual cells, and how they can be used to facilitate distributed RRM and multiple access without any additional overhead. We made several simplifying assumptions, for instance, the deterministic component of the node mobility is aligned in one direction for all nodes, although the cell handovers and the reassignments of node roles were performed. The simulations were only concerned with the link layer protocols, but neither routing nor scheduling was considered, so traffic congestion in the network was not modeled. We investigated the transmission rules where the nodes can only transmit in the channels pre-assigned to the virtual cells whereas there was otherwise no restriction to which communication channels the nodes can listen to. We did not consider how the nodes can further exploit sharing their location information other than in determining their roles within the virtual cells. The interference due to asynchronous transmissions could be mitigated by employing spread-spectrum and multi-antenna techniques.

Much more sophisticated patterns of anchor points could be devised. The hexagonal regular cells are only optimum for very specific mobility model considered. Defining the optimum anchor points for general mobility models is an open research problem. Furthermore, the cluster heads in each virtual cell can adaptively request or advertise additional radio resources in collaboration with the neighboring cells. This could be triggered if the number of nodes in the cell goes above or below defined thresholds. The virtual cells can be adaptively adjusted by changing the number and positions of anchor points, or only some nodes may exploit virtual cells for RRM while other nodes operate under conventional RRM protocols. Such RRM strategies can better match the spatial node distribution over the area with virtual cells. Moreover, the node clusters may not be exactly contained within the virtual cells as considered in our simulations. In this case, a cluster head may be managing multiple virtual cells, or a virtual cell may be managed by multiple cluster heads. Another interesting problem is to investigate the co-existence of multiple MANETs in the area with defined virtual cells, the case of overlay multiple virtual cellular networks, and how to support virtual cells in the upcoming 5G networks. The geographical spectrum management can resolve many spectrum allocation problems.

5. Conclusion

The location information at nodes in wireless networks is becoming a commodity. It is likely that all transmissions in future wireless networks will be linked to exact geographical locations, and the wireless networks may be classified whether the use of location information at nodes is mandatory, optional or not used. The location information is readily available in outdoor environments using the GNSS service. The wireless localization techniques are more complicated to implement, and they consume bandwidth and energy. Hence, it is important to evaluate whether geographical protocols can outweigh these drawbacks. The key motivation for assuming geographical protocols is to improve the network efficiency while reducing the amount of overhead required for setting up and controlling network services, and to generally facilitate better mobility management.

We pointed out that geographical location is a trivial example of context which is naturally shared among the nodes in the network. It can be acquired internally within the network, for example, by means of collaborative localization techniques, or externally with the help of GNSS or terrestrial radio transmitters. There are works which exploit the GNSS timing signal to synchronize the nodes in the network. There may be other context types related to applications, devices or the network itself which can be exploited to improve the network protocols and services. This can be a fruitful area of research to explore in the 5G networks.

Geographical routing protocols were explained how they utilize geographical location information to improve the routing decisions and reduce the number of control messages. Both reactive and proactive routing protocols were discussed and advantages and disadvantages compared. The main challenge as in all other geographical protocols is how to efficiently acquire and share locations of all nodes in the network. This is equivalent problem to acquiring knowledge of all link costs in the network to facilitate optimum routing. Similarly as the link costs change in time, the nodes move and change their locations, so there must be some mechanism how to maintain up to date knowledge of node locations.

Unlike geographical routing protocols, geographical RRM and geographical multiple access did not receive comparable attention in the literature. The concept of virtual cells was proposed to facilitate RRM and multiple access in MANETs without requiring any additional overhead. The virtual cells are defined as Voronoi regions of spatially distributed anchor points. We assumed a two-tier network with clusters fully located in separate virtual cells, and designed a frequency hopping signaling scheme to maintain orthogonal transmissions within clusters of three and seven virtual cells, respectively. We also pointed out that, in all MANETs, the performance of all network protocols is directly affected by the radio propagation conditions, and the mobility of nodes. Finally, we outlined a number of open research problems to further develop the concept of virtual cells.

It should be noted that some topics mentioned in this chapter were treated rather superficially, for example, the mobility management and the localization mechanisms supported in the 4G/5G networks, since our main focus was on the geographical routing and geographical RRM. In addition, the most interesting and comprehensive research problem appears to be how to exploit the location information in MANETs where some mobile nodes are controlled by the 4G/5G network while the other nodes are autonomous and must perform the distributed routing as well as RRM using in-band or out-of-band signaling.

Acknowledgments

The parts of this book chapter were presented in a technical tutorial in the IEEE MILCOM 2018 conference in Los Angeles, CA on 29 October 2018.