Keywords

1 Introduction

By 2020 it is expected that the number of wireless devices will be of order of trillions [1]. With the massive increase of wireless devices and the challenges associated, D2D communication becomes a vital solution. Unlike the existing cellular networks and earlier generations (1G…4G), the future fifth generation (5G) cellular system will employ D2D communication as an enabling technology [2]. Based on the 3GPP report, D2D communication provides a flexible efficient communication paradigm for the future 5G cellular system [3]. Recent research activities in LTE-A also consider to employ D2D communication in the current existing 4G networks [4, 5].

Recently, cellular network operators promote their users to use D2D communication technology to make use of the benefits of the new technology [3]. This results in an increase of the wireless devices support D2D communication. Wireless certified devices support D2D communication reach to 4 million devices in 2017 and are predicted to reach to 10 million in 2018 based on the Wi-Fi alliance watch report [6].

D2D communication enables direct communication between proximate devices without relaying information to the BS [7]. Employing D2D communication in cellular networks achieves lots of benefits, including [8, 26]:

  1. 1.

    D2D communication provides an offloading way for the cellular network,

  2. 2.

    Increases spectrum efficiency,

  3. 3.

    Achieves higher throughput,

  4. 4.

    Reduces the traffic congestion, and

  5. 5.

    Achieves better cell coverage.

D2D communication has two main classifications as illustrated in Fig. 1. In the first classification, D2D communication is categorized based on the spectrum used in the direct communication to two main categories In-band and Out-band D2D communication [7, 27]. In In-band D2D communication, the direct communication is run over the licensed spectrum of cellular system. In another word, the cellular spectrum is used for both cellular communication and D2D communication. The In-band D2D communication can be viewed as underlay or overlay. If D2D communication uses the same resources as cellular system it is referred to as underlay In-band D2D communication. However, in Overlaying a part of cellular spectrum is devoted to the D2D communication. In Out-band D2D communication, the links is initiated over unlicensed spectrum (referred to as a radio interface) using an appropriate wireless technology such as Bluetooth, Zigbee, IEEE 802.11 family [9] and Wi-Fi Direct [10]. If the radio resources are managed and coordinated by the users themselves, the D2D communication is Out-band autonomous. In the other hand, if the BS manages and controls the unlicensed radio resources, the D2D communication is an Out-band controlled [11].

Fig. 1.
figure 1

Classifications of D2D communications.

Full size image

The second classification is based on the degree of involvement of the BS [12]. If the BS controls the communication link, the D2D is either device relaying with base station assisted controlled link or direct communication between devices with base station assisted controlled link. While in the other two types the devices control the communication link themselves.

There are some challenges associated with the implementation of D2D communication technology. The most important challenges are the resource allocation, the interference management and the delay [13, 14]. In this work, a multi-level cluster based autonomous D2D communication protocol is introduced to maintain the in cell communication without the BS. The rest of the work is organized as the following: in Sect. 2 the literature and related work is presented and in Sect. 3 the proposed work is introduced.

2 Related Work

Recently, the research in the area of D2D communications becomes more attractive. D2D communication represents the key solution for current and future cellular systems. Clustering represents the efficient mechanism to employ D2D communication with higher benefits. There are a lot of literatures in clustering and D2D communication, we provide a brief description for the most related works to our proposed work.

In [15], authors concern with the cluster formation and the selection of the cluster heads. The main purpose of the work is to introduce an energy efficient clustering algorithm that reduces the energy consumption through the direct communication process. Thus authors provide a new strategy for changing cluster heads based on their energy. BS is responsible for the selection of the cluster heads and monitoring them. When the energy of a CH goes below a threshold level estimated by the BS, the BS takes the responsibility to select a newer CH with higher energy. The main advantage of the work is the high energy efficiency introduced while in the other hand; the introduced clustering protocol put a great load on the BS as it is mainly dependent on the BS. Another point of view, the work doesn’t consider a certain type of D2D communication and claims that the clustering protocol can be used with all types of D2D. This work must be used in the existence and proper work of the BS unlike our proposed work, also it applies clustering only one time with different mechanism in cluster formation.

In [16], a multi-cast clustering D2D communication protocol is introduced. The authors concern with the cluster head selection, in a way that reduces the blocking probability and increases the power efficiency. The BS controls the clustering inside the cell and decides the decisions of CHs. Simulation results illustrates that the protocol is efficient in terms of blocking probability and energy efficiency. The work makes no sense of D2D communication types and the clustering depends mainly on the BS which remains the main disadvantage of the system.

In [17], a multi-cast clustering D2D communication protocol is introduced such as in [16] but the mechanism of clustering is different. The cluster head selection depends on the data distribution and thus the users who store a multimedia data serve as CHs. The declaration of the CHs is held by the BS.

In [18], a new approach of clustering is introduced. Authors provide a self clustering algorithm based on D2D communication. The cluster formation and CH selection is done using Reed-Solomon (RS) coding and frequency hopping (FH) mechanism. The contribution provides a distribution and illustration for the new idea but without performance metrics. The BS doesn’t involve in clustering process.

In [19], authors introduce an architecture and mathematical model approach for Out-band D2D communication. The interface technology used for direct communication is the Wi-Fi Direct and the cluster formation is done based on the specifications of Wi-Fi Direct. The D2D clustering protocol gives a good simulation results in terms of throughput. Also, authors provides a modification approach for changing CHs based on their energy through the BS in order to achieve a higher energy efficiency. The main advantage of the work is that the BS doesn’t involve in the cluster formation and thus the clustering protocol offloads the cellular load and reduces traffic congestion.

The novelty of the proposed work is that it solves the problem of the BS failure through multi-level clustering. There are no previous work deals with this problem. Also, it is the first time to introduce Multi-level clustering with D2D communication.

3 Proposed Work

The proposed protocol is used to maintain the cell communication in case of the BS failure (due to either a technical problem or a catastrophic situation), thus the vision is to maintain the cell operation without the BS. If the cell users lose the control of the BS they can switch to the D2D proposed protocol. The protocol employs the short range D2D communication as an alternative method to put the hole cell in communication with the neighbouring cells. Beside D2D communication, the cell nodes should be clustered more than once to enable reaching to the neighbouring cells. The main reason for applying clustering multi-times is to make all nodes be able to communicate with the boundary nodes. The boundary nodes are nodes that located at the cell boundary and can communicate directly with nodes in the neighbouring cells. Thus, in order to maintain the cell operation without BS, the proposed protocol employs multi-level cluster based D2D procedures. The idea behind multi-level clustering is to perform clustering between cluster heads of the first level and select some of them to be a second level cluster heads then the second level cluster heads selects some of them to be a third level cluster heads and the procedure goes on until the final level cluster heads [20].

Cluster Formation

Acluster is a group of several users with a CH that acts as the leader of the group and CMs. In the proposed protocol, cluster formation is achieved by users as it is assumed that there is no BS. Multi-level clustering protocol employs clustering more than once based on the cell capacity and the distribution of the nodes inside the cell. First, the first level of clustering is formed and then the levels are formed in descending order. Assume that the protocol performs N levels of clustering, so the first level (L1) is formed first then the last level (LN) and then L(N−1), L(N−2)…..2. In each clustering stage there will be CHs and CMs for different clusters. Figure 2 illustrates the relation between different levels CHs.

Fig. 2.
figure 2

CHs of different levels

Full size image

First Level Clustering

As the clusters are formed inside the cell, they are refereed as intra-cell clusters. All intra-cluster communications run over a WLAN in an unlicensed spectrum. The cell is divided into clusters with a CH (CHL1) and CMs for each cluster; and this is the first level of clustering. The communication inside clusters is Out-band autonomous D2D type as CMs communicate with their CH using Wi-Fi direct.

The first level of clustering is formed based on the announced Wi-Fi Direct specifications [6]. Each Wi-Fi Direct group represents a cluster and the group owner is the head of the cluster. Each CH receives the basic information of its CMs. This information contains the Temporary Mobile Subscribe Identity (M/S-TMSI) and International Mobile Subscriber Identity (IMSI). As a response, each CH forms a schedule that contains all member nodes in its cluster and their details. The schedule data contains the member node identification (CM-ID) allocated by the CH and other received data identifying the member nodes. CHs share their schedules and the downlink traffic with their CMs through a broadcasting message. Figure 3 illustrates the first stage of cell clustering and the cluster heads of the first level are illustrated in Fig. 4.

Fig. 3.
figure 3

First level clustering (L1)

Full size image
Fig. 4.
figure 4

First level cluster heads (CHL1) with the neighbouring cells.

Full size image

Wi-Fi Direct

Wi-Fi Direct is a recent Wi-Fi technology that enables the short range direct communication between devices [10]. Wi-Fi Direct certified devices are assigned a software access point that enables multi-hop communication [21]. Wi-Fi Direct has the following benefits [22, 23]:

  1. 1.

    High Mobility, as the Wi-Fi Direct enabled devices can communicate without Wi-Fi router or access point,

  2. 2.

    Ease of use, due to recent advances in discovery features, users can discover the available devices and services before connection set up,

  3. 3.

    High security,

  4. 4.

    Support the third-party application,

  5. 5.

    Ability to form group work, and

  6. 6.

    Higher throughput due to short range distance.

The proposed work assumes that all devices support Wi-Fi Direct technology. Wi-Fi Direct enabled devices support a mandatory Discovery and power efficient mechanisms and thus, these devices are able of forming Groups or clusters with a group owner that acts as the head of the group (CH). The first stage in forming groups is the device discovery stage. Device discovery is the mechanism used by the devises to find, identify other devices and set up connections with them. The user has the ability to go on the discovery mode at any time (for our work the user will turn automatically to the discovery mode since he lose the BS signal). The group is formed automatically once a connection is established between two devices or more and the members of the group are negotiated to select the CH. Further, details about Wi-Fi Direct cluster formation are presented in [24].

Higher Level Clustering

To set up connections with the neighbouring cells, the first level cluster heads should found their way to communicate directly with nodes in the neighbouring cells. Not all CHs can communicate directly with the neighbouring cells because of the distance and thus higher levels of clustering must be formed. After forming first level of clustering, the final level (level N) of clustering is then formed by the following procedure.

The first step to build the final level of clusters LN is to select the final level cluster heads CHLN. CHs (CHL1) go on a discovery stage to discover which ones are able to reach and communicate with the neighbouring cells. All CHs broadcast a message and wait for a response from any nodes in the neighbouring cells [26]. CHs able to reach to the neighbouring cells, announce themselves as a boundary CHs (BCHs) and those are the cluster heads of the last clustering stage (N) (CHLN). Figure 5 illustrates the CHLNs marked with the yellow colour.

Fig. 5.
figure 5

N-level cluster heads (CHLN) (Color figure online)

Full size image

BCHs form their clusters by broadcasting discovery messages to other first level CHs. CHs of the first level able to receive the message of BCHs respond to the message and announce themselves as cluster members of the last level of clustering CMLN (some of them will be cluster heads of the clustering stage N − 1 (CHL(N−1))). The response is in the form of a responding message contains identification data including M/S-TMSI, IMSI and the number of first level member nodes associated with each one. Each BCH receives respond message from one or more nodes build a table with the identification data of these nodes and give them identifications as CMLN. Thus, the final level (N) of clusters is formed with CHLNs that provides a communication path for them and for CMLNs with the neighbouring cells. Figure 6 illustrates the N-level clusters, CHLNs and CMLNs.

Fig. 6.
figure 6

N-level clusters

Full size image

With the same mechanism, the level N − 1 of clustering is formed. Cluster members of the last clustering level (CMLN) go on a discovery stage and broadcast an advertisement message to the rest of CHL1. CHL1s able to receive the advertisement message of CMLN respond with a message contains the identification data and announce themselves as CML(N−1). CMLNs that receive a response message, announce themselves as CHL(N−1)s and the procedure continues until the (N − 1) clustering level is formed. Figure 7 illustrates the clustering level N − 1 with CHL(N−1)s and CML(N−1)s.

Fig. 7.
figure 7

(N − 1) clustering level

Full size image

The procedure of forming clusters goes on until all CHL1s can reach to BCHs and thus to the neighbouring cells. The number of clustering levels depends on the cell capacity and the distribution of nodes in the cell. The clustering goes to an end only when all CHL1s form parts of a higher level clusters. At this time all nodes in the cell have a communication path to the neighbouring cells and their BSs and thus they can perform all their communication through this way with a proper way and without their cell’s BS. Figure 8 shows an example of a 3-level clustering with a cluster head labelled.

Fig. 8.
figure 8

Example of (3-level) clustering with cluster head labelled

Full size image

4 Conclusion and Future Work

D2Dcommunication achieves many benefits to the cellular system and thus it must be embedded to the existing 4G and the future 5G cellular systems. Behind the benefits, D2D communication can also be used to solve some problems associated with the cellular system; one of them is the BS failure. Employing multi-level clustering with D2D communication is an efficient way to maintain the inter-cell communication without BS. Multi-level clustering gives all nodes inside the cell, communication paths to neighbouring cells and thus can perform all required communication processes. In case of catastrophic situation, the proposed protocol is an efficient way to preserve the cell communication. The worst case is the failure of the BS and those of all neighbouring cells, in this situation the proposed protocol not help. The best case for employing the proposed protocol is the BS failure due to a technical problem or a regional catastrophic situation with all BSs of neighbouring cells are in work.

The future vision is to build a mathematical model for the proposed algorithm and implement it using FPGA to check the performance.