{'fraction_non_alphanumeric': 0.0290957735880607, 'fraction_numerical': 0.005350946866769784, 'mean_word_length': 4.94187779433681, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Selection of efficient relay for energy-efficient cooperative ad hoc networks

The Cooperative Communication (CC) is a technology that allows multiple nodes to simultaneously transmit the same data. It can save power and extend transmission coverage. However, prior research work on topology control considers CC only in the aspect of energy saving, not that of coverage extension. This paper identify the challenges in the development of a centralized topology control scheme, named Cooperative Bridges, which reduces transmission power of nodes as well as increases network connectivity. Previous research on topology control with CC only focuses on maintaining the network connectivity, minimizing the transmission power of each node, whereas ignores the energy efficiency of paths in constructed topologies. This may cause inefficient routes and hurt the overall network performance in cooperative ad hoc networks. With the help of studied topology control problem for energy-efficient topology with cooperative communication. This paper proposed optimum relay nodes selection for CC network to reduce overall power consumption of network.


Introduction
Increasing demand for high-speed wireless networks has motivated the development of wireless ad-hoc networks. In order to fully exploit the technological development in radio hardware and integrated circuits, which allow for implementation of more complicated communication schemes, the fundamental performance limits of wireless networks should be reevaluated. In this context, the distinct characteristics of wireless networks compared to their wired counterpart lead to more sophisticated design of protocols and algorithms. Some of the most important inherent properties of the Physical Layer (PHY) that make the design more complicated include the attenuation of radio signals over long range communications called path loss, and the fading effect caused by multipath propagation. In order to mitigate these effects, the user has to increase its transmission power or use more sophisticated reception algorithms. Another important limitation of wireless performance caused mainly as a result of communication over a limited bandwidth is the interference from other users, communicating over the same frequency spectrum. Wireless ad hoc networks are multi-hop structures, which consist of communications among wireless nodes without infrastructure. Therefore, they usually have unplanned network topologies. Wireless ad hoc networks have various civilian and military applications which have drawn considerable attentions in recent years. One of the major concerns in designing wireless ad hoc networks is to reduce the energy consumption as the wireless nodes are often powered by batteries only. Wireless nodes need to save their power as well as sustain links with other nodes, since they are battery powered. Topology control deals with determining the transmission power of each node so as to maintain network connectivity and consume the minimum transmission power. Using topology control, each node is able to maintain its connection with multiple nodes by one hop or multi-hop, even though it does not use its maximum transmission power. Consequently, topology control helps power saving and decreases interferences between wireless links by reducing the number of links. Topology control [1][2][3][4] is one of the key energy saving techniques which have been widely studied and applied in wireless ad hoc networks. Topology control lets each wireless node to select certain subset of neighbors or adjust its transmission power in order to conserve energy meanwhile maintain network connectivity. Topology control have been widely studied and applied in wireless ad hoc networks as one of the key energy saving techniques. In order to save energy and extend lifetime of networks topology control lets each wireless node to select certain subset of neighbors or adjust its transmission power meanwhile maintain network connectivity. Recently, a new class of communication techniques, cooperative communication (CC) [37], [38], has been introduced to allow single antenna devices to take the advantage of the multiple-input-multipleoutput (MIMO) systems. This cooperative communication explores the broadcast nature of the wireless medium and allows nodes that have received the transmitted signal to cooperatively help relaying data for other nodes. Recent study has shown significant performance gain of cooperative communication in various wireless network applications: energy efficient routing [39]- [41] and connectivity improvement [42]. In this paper, we study the energy efficient topology control problem with CC model by taking the energy efficiency of routes into consideration. Taking advantage of physical layer design that allows combining partial signals containing the same information to obtain the complete data, we formally define cooperative energy spanner in which the least energy path between any two nodes is guaranteed to be energy efficient compared with the optimal one in the original cooperative communication graph. We then introduce the energy-efficient topology control problem with CC (ETCC), which aims to obtain a cooperative energy spanner with minimum total energy consumption, The cooperative communication techniques can also be used in topology control. In [35], Cardei et al. first studied the topology control problem under cooperative model (denote by TCC) which aims to obtain a strongly-connected topology with minimum total energy consumption. They proposed two algorithms that start from a connected topology assumed to be the output of a traditional (without using CC) topology control algorithm and reduce the energy consumption using CC model. The first algorithm (DTCC) uses 2-hop neighborhood information of each node to reduce the overall energy consumption within its 2-hop neighborhood without hurting the connectivity under CC model. The second algorithm (ITCC) starts from a minimum transmission power, and iteratively increases its power until all nodes within its 1-hop neighborhood are connected under CC model. Observing that the CC technique can also extend the transmission range and thus link disconnected components. In [36], Yu et al. applied CC model in topology control to improve the network connectivity as well as reduce transmission power. Their algorithm first constructs all candidates of bidirectional links using CC model (called cooperative bridges) which can connect different disconnected components in the communication graph with maximum transmission power. Then they apply a 2-layer MST structure (one MST over the CC links to connect the components, the other is inside each component) to further reduce the energy consumption.

Related Work
Topology control has drawn a significant amount of research interests in wireless ad hoc networks [6][7][8][9][10][11][12]. Primary topology control algorithms aim to maintain network connectivity and conserve energy by selecting certain subset of neighbors and adjusting the transmission power of wireless nodes. Comprehensive surveys of topology control can be found in [1][2][3][4]. Cooperative communication (CC) exploits space diversity through allowing multiple nodes cooperatively relay signals to the receiver so that the combined signal at the receiver can be correctly decoded. Since CC can reduce the transmission power and extend the transmission coverage, it has been considered in topology control protocols. However, prior research on topology control with CC only focuses on maintaining the network connectivity, minimizing the transmission power of each node, whereas ignores the energy efficiency of paths in constructed topologies. This may cause inefficient routes and hurt the overall network performance in cooperative ad hoc networks. Paper [43] address this problem, author introduce a new topology control problem: energy-efficient topology control problem with cooperative communication, and propose two topology control algorithms to build cooperative energy spanners in which the energy efficiency of individual paths are guaranteed. Both proposed algorithms can be performed in distributed and localized fashion while maintaining the globally efficient paths. Cooperative communication (CC) allows multiple nodes to simultaneously transmit the same packet to the receiver so that the combined signal at the receiver can be correctly decoded. Since CC can reduce the transmission power and extend the transmission coverage, it has been considered in topology control protocol. However, prior research on topology control with CC only focuses on maintaining the network connectivity, minimizing the transmission power of each node, whereas ignores the energy-efficiency of paths in constructed topologies. This may cause inefficient routes and hurt the overall network performance. Paper [44] introduces a new topology control problem: energy-efficient topology control problem with cooperative communication, and propose two topology control algorithms to build cooperative energy spanners in which the energy efficiency of individual paths are guaranteed. Chen and Huang [5] first studied the strongly connected topology control problem, which aims to find a connected topology such that the total energy consumption is minimized. They proved such problem is NPcomplete. Several following works [8][9][10][11][12] have focused on finding the minimum power assignment so that the induced communication graph has some "good" properties in terms of network tasks such as disjoint paths, connectivity or faulttolerance. On the other hand, several localized geometrical structures [13][14][15][16][17][18] have been proposed to be used as underlying topologies for wireless ad hoc networks. These geometrical structures are usually kept as few links as possible from the original communication graph and can be easily constructed using location information. Recently, a new class of communication techniques, cooperative communication (CC) [19], [20], has been introduced to allow single antenna devices to take the advantage of the multipleinput-multiple-output (MIMO) systems. This cooperative communication explores the broadcast nature of the wireless medium and allows nodes that have received the transmitted signal to cooperatively help relaying data for other nodes. Recent study has shown significant performance gain of cooperative communication in various wireless network applications: energy efficient routing [21][22][23][24], broadcasting [25][26][27], multicasting [28], connectivity/coverage improvement [29], [30], and relay selection for throughput maximization or energy conservation [31][32][33][34].

Cooperative Communication
Wireless communication technique with a wireless network, of the cellular or ad hoc selection, where the wireless users, may increase their valuable quality of service via cooperation a cooperative communication system, each wireless user is assumed to transmit data as well as act as a cooperative agent for an additional user (Fig. 1). For example, in figure 1, node S is unable to communicate with node D, since D is out of its maximum transmission range of S. On the other hand, S can send a cooperation request message and data to adjacent connected nodes R as relay node and then the three nodes all together pass on the data to D. Therefore, D can receive it due to the extended transmission range of nodes S, R, and R.

Figure 1. Coverage Extension using CC
Cooperative communication means in any system users share and cooperative their resources to enhance their performance jointly with help of each other. This method is very useful for enhance transmission range of a node in mobile adhoc network as diverse channel quality and limited energy and limited bandwidth limitations wireless environment. Due to cooperation, users that know-how a deep weaken in their connection towards the target can utilize quality channels provided by their partners to achieve the preferred quality of service (QoS). This is also identified like the spatial diversity gain, which is in the same way achieved in multiple-input-multiple-output (MIMO) wireless systems. Cooperation has an interesting trade-off between code rates and transmits power. In the case of power, extra power is needed because to every user, when system is in cooperative mode, is transmitting for both users. But transmits power for both users will be reduced because of diversity. Due to this trade-off, one hopes for a net reduction of transmit power, given every-thing else being constant. In cooperative communication every user sends both his/her personal bits as well as a few data for his/her neighbor; one may believe this causes loss of rate in the system. However, the spectral efficiency of each user improves because; due to cooperation diversity the channel code rates are able to be improved. Hence one more trade-off is occurred. So whether cooperation is worth the incurred cost, has been studied positively by numerous research studies.

Cooperative Model
Here, we explain a cooperative communication model and a network representation for topology control system. In addition, we define two problems: Topology Control considering Extended Links caused by CC and Energy-Efficient Extended Link with CC.

Cooperative Communication Model
In Cooperative Communication Model PMAX represents every node's maximum transmission power limit. Pi is the transmission power of node i. α is the path loss exponent and τ is the minimum average SNR for decoding received data. dij is the distance between node i and node j. For a source node i to communicate with node j directly (figure 1), they must satisfy

Pi (dij) −H ≥ τ (Pi ≤ PMAX).
H denotes the set of a source node and helper nodes. If nodes in H transmit simultaneously, i.e., use cooperative communication, the following formula must be satisfied for correct decoding at destination node j.
i∈H Pi(dij)−H ≥ τ (Pi ≤ PMAX) CC leads to extended transmission coverage. For example, in figure 1, node S cannot communicate with node D, since D is out of the maximum transmission range of S. Node S can send a cooperation request message and data to nodes R and R, and then the three nodes simultaneously transmit the data to D. Therefore, D can receive it due to the extended transmission range of nodes R, R, and S. The physical layer issues including synchronization for implementing the CC technique can be found in [8]. In figure 1, if node R applies CC with partner S in sort to communicate with D, which is already accessible to R by straight links, the network can decrease the sum of node transmission power. Cardei et al. [26] focus their problem formulation on saving power with CC, not extended CC links.

Network Model
The wireless network topology is form as a 2-dimensional graph is collection of vertices V and edges E, graph G = (V, E). V = (v1, ..., vn) is a set of random nodes and E is a set of pairs of nodes as link between them (vi, vj), with vi, vj ∈ V. The notations V (G) and E (G) are used for the vertex-and edge-set of G. The weight of a directional link from u to v is denoted as w (u → v). Edge (u, v) has weight, w (u, v), which indicates the average power utilization for maintaining a bi-directional link (u, v). N (v) is the set of neighbor nodes within the maximum transmission range of node v. All elements in N (v) are the candidate nodes, which are eligible as helper nodes for v. Node v is capable to communicate directly with its neighbors within 1 hop. R(u) is the set of nodes which are accessible to node u by 1-hop or multi-hop, i.e., have a path to a node u.

Problem Formulation
Major difficulty in given a wireless multi-hop network G=(V,E) which is restricted under CC connection model, it that assign transmission power Pi for every node vi such that make topology G' from this power assignment is a cooperativeenergy t-spanner of G and the sum of transmission power of all nodes, ΣviεVPi , is minimized. Key point is that the spanner property also guarantees that the induced topology G' is strongly connected under CC model. Paper [43] presents an Energy-Efficient Topology Control in Cooperative Ad Hoc Networks, but if neighbor nodes are more for any node so they all will help to source node for transmitting data to destination whether only some nodes of them as capable to transmit data till destination so power of other nodes are unnecessarily used during this transmission as given in figure 2.

Proposed Work
This paper proposed efficient in two phase first phase is to Energy-efficient topology control with cooperative communication and then optimum relay node selection. First phase propose two topology control algorithms which build energy-efficient cooperative energy spanners. To keep the proposed algorithms simple and efficient, we only consider its one-hop neighbors as possible helper nodes for each node when CC is used [43]. Thus, the original cooperative communication graph G contains all direct links and CC links with one hop helpers, instead of all possible direct links and CC-links. In addition, for each pair of nodes vi and vj, we only maintain one link with least weight if there are multiple links connecting them. Here, all links are directional links. Both proposed algorithms are greedy algorithms. The major difference between them is the processing order of links. The first algorithm deletes links from the original graph G greedily, while the second algorithm adds links into G'' greedily. Here, G00 is a basic connected sub graph of G. Both algorithms can guarantee the cooperative energy spanner property of the constructed graph G'.

Greedy Method for Deleting Links from Network Graph
Step 1: Construction of G. Initially, G is an empty graph. First, add every direct links vivj into G, if node VI can reach node VJ when it operates with PMAX. Then, for every pair of nodes vi and vj, we select a set of helper nodes Hij for node vi from its one-hop neighbors N (vi), such that the link weigh w (vi,vj) of the constructed CC-link is minimized. Notice that this helper node decision problem is challenging even under our assumption that the transmission powers of VI and its helper node set to maintain CC-link are the same. If we try all combinations of the helper sets to find the optimal helper set which minimizes the total energy consumption of vi and its helpers, the computational complexity is exponential to the size of the one-hop neighborhood N (vi). It is impractical to do so in case of a large number of neighbors. Therefore, we directly use the greedy heuristic algorithm Greedy Helper Set Selection (vi, N (vi), vj), to select the helper set Hij. Then, we compare w (vivj) with p (PG(vi,vj)) which is the current shortest path from node vi to node vj in G. If w (vivj) ≤ p (PG (vi,vj)) and Add this CC-linkg vivj into G. If there already exists a direct link vivj, delete it after the new CC-link g vivj is added (since it costs more energy than the CC-link). Notice that if Node vi cannot communicate with node vj within one-hop even in CC model.
Step 2: Construction of G'. Copy all links in G to G', and sort them in the descending order of their weights. Start to process all links one by one and delete the link vi vj from G' if G-vivj is still a cooperative energy t-spanner of G. Hereafter, we use G-e or G+e to denote the graph generated by removing link e from G or adding link e into G, respectively. In addition, when a CC-link g vivj is kept in G', all its helper links must be kept in G' too.
Step 3: Power Assignment from G'. For each node vi, its transmission power is decided by the following equation: Here and are the energy consumption at vi for a direct link vivj and a CC-link vivj , respectively.

Greedy Method for Adding Links
The second topology control algorithm starts with a sparse topology G'' which is strongly connected under CC model. We can use the output of the algorithm in [36] as the initial topology. Then, we gradually add the most energy-efficient link into G''. Here, the energy-efficiency of a link is defined as the gain on reducing energy stretch factors by adding this link. Our algorithm will terminate until the constructed graph G' satisfies the energy stretch factor requirement. The detail steps are summarized as follows: Step 1: Construction of G and G''. The step of constructing G is the same as the one in Algorithm 1. Then, we call the algorithm in [36] to generate G'', a connected sparse sub graph of G.
Step 2: Construction of G'. Initialize G'=G'', for every link vivjεG but not G', compute its stretch-factor-gain g G'G (vivj) as follows: In other words, the total gain of a link vivj is the summation of the improvement of stretch factors of every pair of nodes in G' after adding this link In each step, we greedily add the link with the largest stretch-factor-gain into G'. If there is a tie, we use the link weight to break it by adding the link with the least weight. We repeat this procedure until G' meets the stretch factor requirement t.
Step 3: Power Assignment from G'. For every node VI, assign its power level Pi using equation for Pi.

Optimum Relay Nodes Selection
Once communication topology has been created optimum nodes can be selected from this topology for efficient transmission. As problem definition mention in example in figure 2(a) according to CC model if S sends packets to D which is not in transmission range of S because of power saving fixed transmission range but it can be increase its transmission range with help of its relay nodes and transmit packets. In this example node S uses its all 1-hop neighbors where as other hand only few nodes are enough for sending data till D. hence power of other nodes are useless for this communication if ΣviεVPi for selected neighbors of node S.

Figure 2. Demonstration to reduce energy consumption in CC ad-hoc network
We propose two topology control algorithms which build energy-efficient cooperative energy spanners. To keep the proposed algorithms simple and efficient, we only consider its one-hop neighbors as possible helper nodes for each node whenCCis used. Thus, the original cooperative communication graph G contains all direct links and CClinks with one hop helpers, instead of all possible direct links and CC-links. In addition, for each pair of nodes vi and vj, we only maintain one link with least weight if there are multiple links connecting them.

Conclusion
In this paper, we deliberate a topology control problem in detailed, energy-efficient topology control problem with cooperative communication, which aims to keep the energyefficient paths in the constructed topology. Also key point has been discussed as in wireless ad-hoc network for effective energy transmission. In this paper, we introduced a new topology control problem: optimum relay selection topology control problem with cooperative communication, which aims to keep the energy efficient paths in the constructed topology and reduce power consumption in network. In future this scheme is implemented and tested in real simulation for result gathering. This paper proposes novel algorithm for optimum relay selection rather selecting all nodes only those nodes will be selected which are capable for large enough to make transmission range within destination node to save power of other nodes hence overall network power consumption is minimize. Every node also store power level of every neighbor node in routing table with routing information. For transmit data packets relay selection is based on highest power level nodes. The nodes having maximum power level in direct neighbor selected for relay transmission. As given in figure 2(b) proposed algorithm can be given as follow. This will helpful for saving battery power for other nodes in to reduce overall network power consumption.