A VMIMO-Based Cooperative Routing Algorithm for Maximizing Network Lifetime

Ji Zhang , Dafang Zhang ＊, Kun Xie ,2, Hong Qiao , Shiming He

1 College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China

2 Department of Electrical and Computer Engineering, State University of New York at Stony Brook, New York 11794, NY, USA

3 School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha, China

I. INTRODUCTION

Nodes in Wireless Sensor Networks (WSNs)always get power from batteries, and it is difficult for them to update or charge their batteries for two reasons: (1) it will cost much time and money to recycle batteries after widespread development; (2) recycling is limited by particularity of some special environment (such as disaster area). Hence, prolonging network life by improving energy efficiency is an important issue in WSNs.

Most current wireless transmission is based on SISO (Single Input and Single Output),and has drawbacks of high retransmission and power consumption. In order to address the problem, researchers propose CC (Cooperative Communication) technique [1-3] to obtain spatial diversity gain. CC sends or receives data by a virtual antenna array with antennas of other users, which can reduce energy consumption of data transmission effectively and prolong network lifetime.

Cooperative routing (CR) is a cross layer routing scheme by jointing cooperative communication technology in the physical layer and routing technology in the network layer.In order to improve network performance, the CR algorithm [4-12] is used to select a cooperative route in flows and allocate power for nodes in the route. Energy-efficient CR aims to reduce energy consumption of end-to-end transmission [13-22] or prolong network lifetime [23-27]. Compared with the traditional routing, these CR algorithms can save energy and prolong the lifetime of the network. However, Virtual Multi-Input Single–Output(VMISO) based CR algorithms [13-16,23-24] can’t take the full advantage of saving energy and further prolonging network life since the only one single choice in the selection of cooperative transmission mode.

Currently, VMIMO based CR algorithms,Cooperative Multi-input Multi-output (CMIMO) [17, 18] and heterogeneous aware based cooperative MIMO transmission algorithms[26] are only suitable for clustering network.Energy-efficient Cooperative Geographic Routing (ECGR) [27] is limited by geographic distribution of sensor nodes. The CwR [19]routing algorithm whose objective is to minimize energy consumption of end-to-end transmission, cannot deal with the premature death of the network while some nodes exhausted their energy. Current VMIMO based on CR algorithms aren’t designed for prolonging network lifetime, and don’t consider the channel quality and remaining energy of nodes. These routings of the network may be dead prematurely while some popular nodes exhausted energy. In order to further improve network lifetime, this paper proposes a VMIMO based cooperative power allocation strategy to balance the energy consumption among the nodes in the single-hop transmission, and designs a new VMIMO Cooperative Routing Algorithm(VMIMOCR) to improve the lifetime of the network. The basic idea of the algorithm is as follows:

Firstly, for each node, the algorithm chooses an optimal set of cooperative relay nodes from neighbors with their state information,and constructs virtual node with these optimal set of cooperative nodes.

Secondly, with the extension of cooperative power allocation strategy of VMIMO,the algorithm balances the energy cost among senders of the virtual node, calculates the cost of the virtual link to determine optimum forwarding paths.

The algorithm determines the participating nodes in each hop, the energy allocation and the route of the entire transmission by four steps: finding cooperative neighbors, node virtualization, link virtualization and selecting the shortest path.

The performance of the proposed algorithm is evaluated by comparing the proposed algorithm with three categories of algorithms including routing algorithms based on traditional communication (Minimum Total Energy, MTE [29] and Flow Augmentation, FA[28]), cooperative routing algorithms based on VMISO (Cooperative Shortest Path, CSP [14]and Flow Augmentation Cooperative Routing,FACR [23]) , cooperative routing algorithm based on VMIMO(CwR routing algorithm[19]). The simulation results show that, in the network, VMIMOCR improve the network lifetime from 37% to 348%.

By considering initial energy, remaining energy and channel state, the authors propose a solution of cooperative relay node selection based on VMIMO cooperative communication model, power allocation, cooperative path finding, and design a cooperative algorithm-VMIMOCR.

II. RELATED WORKS

CC is new spatial diversity technique, which makes nodes transmit data cooperatively to improve network performance. As an attempt on exploiting cooperative communication in routing design, CR has attracted increasing attention of researchers. At the beginning, CR is proposed to solve network security problem. Currently, more and more CR researches delve into saving network energy. According to different purposes, energy-efficient CR can be classified into two categories:

The first one is to minimize end-to-end transmission energy consumption[13], such as PC (Progressive Cooperation), CAN (Cooperation Along the Minimum Energy Non-Cooperative Path), CSP (Cooperative Shortest Path)[14], MPCR (Minimum Power Cooperative Routing) [15], GSPRA (Generalized the standard Shortest Path Routing Algorithm) [16],CMIMO, CwR and MCCR (Minimum Collision Cooperative Routing) at al. PC is similar to CAN. Both of them firstly select the shortest path directly, and then choose cooperative relay nodes for links in forwarding paths. PC can save more energy than CAN, but it is more complex than CAN. CSP is built on Dijkstra,and plus cooperative characteristics into relax stage. MPCR can minimize the energy consumption under the condition of guaranteeing network throughput, but it just supports single cooperative relay. GSPRA is a distributed cooperative routing algorithm based on VMIMO. CMIMO is a cluster-based cooperative algorithm. CwR firstly selects a shortest direct route, and then employs cooperative relays for links in these routes. MCCR considers the hidden problem and exposure problem, and effectively reduces end-to-end energy consumption by minimizing collision probability among multiple flows. However, all of them only consider minimizing energy consumption of single or multiple end-to-end flows, and not consider remaining energy of the overall network. Although energy consumption of these flows is minimal, some nodes in the core area may exhaust their energy very soon and network lifetime will be short.

The second one is intended to maximize network lifetime [23-27]. The network lifetime is primarily determined by the time that the first node e exhausted their energy. Hence,minimizing overall network energy consumption doesn’t mean the lifetime will be prolonged. By combining the Flow Augmentation routing algorithm, [23] proposes a centralized cooperative routing algorithm-FACR (Flow Augmentation Cooperative Routing) to maximize network lifetime. [24] proposes a weighted power allocation method MNLCR(Cooperative Routing Algorithms for Maximizing Network Lifetime). Both FACR and MNLCR are based on VMISO, and can’t take advantage of cooperative transmission. [25] aims to maximize network lifetime of broadcasting tree. [26] proposes a cooperative MIMO transmission algorithm based on heterogeneous aware. In order to save energy consumption and prolong network lifetime, the algorithm uses cluster heads to employ cooperative relay nodes to transmit data cooperatively. However,it is only suitable for clustering network. [27]proposes ECGR. Depending on geographic information, the algorithm selects cooperative relay nodes to prolong transmission range at each hop. Nevertheless, the performance of ECGR is depended on the static distribution of nodes.

Fig. 1 VMIMO cooperative transmission model

Existing cooperative algorithms may cause the premature death of the network by exhausting the energy of some hot nodes. In order to solve the problem, this paper considers nodes’ remaining energy and channel quality,and proposes a novel power allocation strategy to maximize network lifetime. Based on the new power allocation strategy, a cooperative routing algorithm based on VMIMO is designed to maximize network lifetime.

III. SYSTEM MODEL AND PROBLEM

As shown in Figure 1, this paper adopts VMIMO cooperative transmission model. There are two nodes sets: the sender set and the receiver set. Each set contains K nodes, and here K is 3. Nodes in the receiver set can receive signals from all nodes in the sender set. The transmission is synchronous and all nodes in the sender set have data needed by receivers. Besides, all nodes can adjust their transmission power, and each node in the sender set can combine signals from multiple nodes in the sender set. We do not address the feasibility of precise phase synchronization as other cooperative routing algorithms. This is just an idealization made for the simplicity and theoretical tractability provided by it. Several approaches were proposed to solve the synchronization issue [30].

Figure 2 shows the cooperative forwarding paths based on VMIMO model. The source node sends data to destination via multiple virtual antenna arrays. The data is sent cooperatively from one VMIMO model to another VMIMO until reaches the destinaion.

Figure 3 shows a wireless sensor network.We useG=(V,L) represents the undirected graph, whereVrepresents the node set, andLrepresents the link set. In the network, each node has limited energy.EtandRirepresent initial energy and remaining energy of nodei. And network lifetime is defined as the time duration from the moment that network starts work to the moment that the first node exhausts its energy. If two nodes can communicate with each other, there is one link between them. Any two nodes can exchange data through multiple hop cooperative transmission. Each node can adjust their transmission powerPt. When theSNR(Signal to Noise Ratio) in the receiver node is larger than thresholdSNRmin, the receiver node can decode the data correcly.

This paper wants to design an algorithm based on VMIMO that can solve the problem of cooperative relay node selection [31], power allocation [32,33] and cooperative routing to maximize network lifetime.

IV. ALGORITHM MOTIVATION

Let’s illustrate the motivation by an example.Like Figure 4, there areNnodes in the network and the source node s needs to send data to the destination noded. Node 1, 2 and 3 are in the communication range of node s. The remaining energy in node 3, 5 and node 8 is 30%, 100%, and 100% respectively.

Generally, cooperative routing algorithms based on VMIMO determine routes through two stages. Firstly, a direct route is chosen by using traditional routing method (AODV,DSR), such as{s→2→5→7→d}. Secondly,select cooperative relay nodes for multi-hop in the direct forwarding path as VMIMO to transmit data cooperatively. For example, node 5 employs node 4 and node 6 as its cooperative relay nodes by sending a HELLO message.Like Figure 4, the VMIMO cooperative route is {s→(1,2,3)→(4,5,6)→(7,8)d}.

Fig. 2 Route based on VMIMO cooperative transmission model

Fig. 3 Wireless sensor network

Fig. 4 Network model

VMIMO cooperative transmission model can effectively save energy consumption, and prolong the network lifetime to some extent.But, previous method firstly determines the main path of direct transmission and ignores the influence from cooperative relay nodes.And it has encountered three problems as follows, which cause that it can’t fully play the advantages of CC.

Firstly, it doesn’t consider neighbors of nodes in the main path, which affects em-ploying cooperative relay nodes. For instance,node 7 can only employ one neighbor node 8 with deficient energy. At worst, nodes in main path have no neighbor and it has to use direct transmission to send data.

Secondly, at each hop, power allocation is no different between nodes with enough energy and nodes with deficient energy. Like Figure 1, if the channel quality of all nodes is the same, node 1,2,3 will use the same transmission power via previous method. But node 3 has only 30% energy, while node 1 and node 2 have 100% energy. Hence, when the network dead, that is, node 3 exhausted its energy quickly, but node 1 and 2 still remained 70%energy.

Thirdly, if energy of nodes in the main path is not enough, optimal solution of cooperative relay nodes selection can’t extend network lifetime fundamentally. Like Figure 4, because node 5 has deficient energy, the network will be dead soon, even if the best cooperative relay node has been selected.

Therefore, we are required to solve these three problems. Specifically, 1) how to select cooperative relay nodes for multi-hop relay nodes; 2) how to allocate transmission power for senders to balance energy consumption among cooperative nodes with initial energy,remaining energy and channel state; 3) how to find optimal cooperative routes.

And in order to solve these problems, this paper proposes a cooperative routing algorithm based on VMIMO for maximizing network lifetime.

The main idea of our algorithm is: Optimal cooperative relay node set is selected with neighbors’ state information, and virtual nodes are formed by combining the sender and its cooperative relay nodes. With initial energy,remaining energy and channel state, power allocation strategy is designed to maximize network lifetime. And the algorithm is accomplished through four steps: finding cooperative neighbors, node virtualization, link virtualization and selecting the shortest path.

Next, we’ll describe the detail of the algorithm.

V. ALGORITHM DESIGN

The proposed VMIMOCR cooperative routing algorithm is based on VMIMO cooperative transmission model, aiming to maximize network lifetime. In this section, we will describe the algorithm, and then express four steps of the algorithm.

In the network, each node can employ cooperative relay nodes within transmission range of transmission powerPintra, and communicate with nodes within transmission range of transmission power Pinter. At the beginning, we express the concept of the virtual node and the virtual link.

Virtual nodeis the set of the node and its cooperative relay nodes. If a node does not have any cooperative relay node, the virtual node just contains the node itself.

Virtual linkis the link between the virtual node and virtual node. There are 4 types of link: VSISO (Virtual Single-Input Single-Output), VSIMO (Virtual Single-Input Multi-Output), VMISO (Virtual Multi-Input Single-Output), and VMIMO (Virtual Multi-Input Multi-Output).

According to the idea of Section 4, the VMIMO can be divided into four steps.

First step: finding cooperative neighbors.Each node collects its neighbors’ information,such as ID, remaining energy and cooperative neighbors list.

Second step: Nodes virtualization. According to neighbors’ state information, optimal cooperative relay node set is selected. And virtual nodes are constructed by combining multi-hop relay node with cooperative relay nodes.

Third step: Link virtualization. Power allocation strategy is decided for the sender of each virtual link, and transmission cost of the link is calculated.

Fourth step: Finding shortest path. The optimal route is established based on transmission cost of virtual links.

Next, we’ll describe the detail of the algorithm.

5.1 Finding cooperative neighbors

Nodes exchange information by sending a HELLO message. According to the reply message, nodes store ID and remaining energy of available cooperative nodes in their cooperative neighbors list.

Similar to other routing algorithm, once get the channel resource, node v sends HELLO message to its neighbors with constant powerPintra, and the HELLO message includes current node ID, remaining energy and cooperative neighbors list of nodev. When nodeureceives the message from nodev, nodeuchecks whether its cooperative neighbors contain node v. If not, nodeuadds nodev’s information into its cooperative neighbors list,otherwise updates nodev’s remaining energy.

Nodeuwill send a HELLO message while encountering two conditions. First is possible that node u receive HELLO message from a new neighbor, and u will update its cooperative neighbors list and broadcasts the update to its neighbors. The second is that nodev’s cooperative neighbors list doesn’t include nodeu’s information, anduwill send HELLO message tovwhen u receives HELLO message fromv. In a stable network, nodes can obtain its cooperative neighbors information by exchanging several HELLO message.

After waiting for a period of time, nodeuwill proceed to the next step if it doesn’t receive update message from its neighbors. And this mechanism can ensure that the process of finding cooperative neighbors can be completed in a certain time.

5.2 Node virtualization

After finding cooperative neighbors, each node should select several cooperative relay nodes to accomplish VMIMO communication. Because cooperative relay nodes need to consume extra energy to complete cooperative communication, remaining energy is an important issue for selecting cooperative relay nodes.

Cooperative neighbors list contain the remaining energy information of neighbors.

If one node can employ at most two cooperative relays nodes to transmit data, the node will choose two nodes with most remaining energy from its cooperative neighbors list.We denote node u and its two cooperative relay nodevandwas a node set (u,v,w), and define the node set as a virtual nodeu’. We describeuas a master node ofu’, and denote remaining energy ofu’asRu’caculated as average remaining energy ofu,v,w, that is,Ru’=(Ru+Rv+Rw)/3.

Let’s illustrate the process of node virtualization by Figure 5. In Figure 5, there are 16 nodes evenly distributed in the network,and both vertical and horizontal are 1. And communication distance of cooperative relay nodes is 1 (the longest communication range under transmission powerPintrais 1), communication among nodes is((The longest communication range under transmission powerPinteris 1). Digital below the node represents the node index, and the digital in node represents remaining energy. For example,node 6 can employ node 2, 5, 7 and 10 as its cooperative relay nodes. According to nodes’remaining energy, node 6 will select node 2 and 7 with 0.8 remaining energy as its cooperative relay nodes. And node 6, 2, 7 will form a virtual node 6’, whose remaining energy isR6’=(0.4+0.8+0.8)/3=0.67. In the same way,virtual nodes corresponding to other nodes can be constructed and their energy can be calculated, like Figure 6.

Fig. 5 Network topology

Fig. 6 Virtual node state information

Fig. 7 Link transmission mode

In order to calculate the virtual link costs,Virtual nodes need to exchange state information through vHELLO message. The vHELLO message carries the following: virtual node ID,the member nodes ID, remaining energy of the member nodes and link costs of the member nodes. The operation mode of the vHELLO message is similar to the HELLO message.

5.3 Link Virtualization

Each virtual node can be seen as a virtual antenna array, and the link between two virtual node can be seen as a virtual link. If master node u and master nodevcan communicate with each other, virtual nodeu’and virtual nodev’can also communicate with each other. Cooperative routes with maximal lifetime are composed of multi-hop virtual links. And in order to select optimal cooperative routes,power allocation strategy and virtual link cost should be determined.

Generally, nodes distribution is different,and nodes can employ different number of cooperative relay nodes. At worst, nodes may not employ cooperative relay nodes in the spare area. The virtual link can be classified into four types according to the number of virtual antennas. Like Figure 7(a), when the sender and receiver have no cooperative relay node to employ, VMIMO will become traditionally direct transmission model, and the virtual link is VSISO link. In Figure 7(b), when sender can’t employ cooperative relay nodes, VMIMO becomes broadcasting model, and the virtual link is VSIMO link. In Figure 7(c), when the receiver employs no cooperative relay nodes,the virtual link is VMISO link. In Figure 7(d),both the sender and receiver employ cooperative relay nodes, and the virtual link is VMIMO link.

Next, we’ll describe the power allocation strategy for senders of each virtual link and determine the transmission cost for virtual links.

5.3.1 Power allocation strategy

L’is the virtual link between virtual nodeu’and virtual nodev’, and the sender set isS={u’}, and the receiver set isT={v’}. The master node ofu’isu, and the master node ofv’isv. If virtual linkL’is VSISO or VSIMO link,S={u}. If virtual linkL’is VSISO or VMISO link,T={v}. WhenSsends data toT,any nodetinTcan receive the signalas follows:

Most routing algorithms (such as CAN,CSP) minimum total power. But, nodes in the sender set possess different initial energy Ei and remaining energy Ri. In order to prolong network lifetime, nodes with deficient energy should not consume too much energy for transmission. Hence, power allocation strategy should not only pursue minimum total power, but also consider both initial energy and remaining energy of the sender. Hence, we propose a cooperative power allocation strategy based on VMIMO for maximizing network lifetime, targeting at minimal weighted transmission power. And the weight has a positive correlation with initial energy and negative correlation with remaining energy, like formula (2).

whereXis weighted parameter. (2) defines the weighted relationship among the ratio of initial energyEi, remaining energyRiand transmission power. IfXis large, power allocation strategy will emphasize more the ratio of initial energy than remaining energy; otherwise,power allocation strategy pay more attention to the transmission power. WhenXequals 0,the strategy just considers transmission power,and this is minimal total power strategy. And VMIMO cooperative transmission model is based on the idea.

Each node in the sender setScan adjust its transmission power under the restriction of rated power, and this constraint condition is describe as (3)

When SNR is larger thanSNRmin, receiver nodetcan decode data correctly. And (2) can express this constraint. The number of the constraint is equal to the number of nodes in the receiver set.

Hence, by jointing objective function (2)and constraint conditions (3), (4), the power allocation problem can be described as a convex optimization problem defined in (5).

5.3.2 Virtual link cost

In order to extend network lifetime, the cost of virtual links in the cooperative routes should not only consider the transmission power, but also consider virtual nodes’ initial energyEu’and remaining energyRu’.Hence, we define the cost of virtual linkL’asin(6).

And the master node of virtual nodes calculates the cost of the virtual link among virtual nodes.

In Figure 8, the cost of virtual link between virtual node s’ and virtual node 2’ is:

There are 7 virtual links outgoing from virtual s’, which connect virtual node 2’, 3’, 5’, 6’,7’, 9’, 10’ respectively. The cost of these virtual link is 0.7, 2.23, 0.73, 1.09, 2.51, 2.28 and 2.56. After calculating the cost of all virtual links, the shortest paths between s’ and d’ can be selected.

5.4 Finding the shortest path

After link virtualization, we can get a virtual network composed of virtual nodes and virtual links. And then the shortest path between source s and destination d can be selected by using traditional routing method, such as Dijkstra, Bellman-Ford.

Fig. 8 Virtual link cost

Fig. 9 Final cooperative route

According to the cost of virtual links, the shortest path between s and d: {(s,2,5)→(2,s,3)→(7,3,8)→(12,8,d)→d}. Furthermore,we need to adjust the selected cooperative routes: (a) in the first hop, master node s firstly needs to send message to its cooperative relay nodes 2 and 5; (b) when virtual node (12,8,d)receives data, destination d can also overhear the data and the last hop {(12,8,d)→d} can be deleted. At last, the final cooperative route is{s→(s,2,5)→(2,s,3)→(7,3,8)→(12,8,d)}, like Figue 9.

5.4.1 Distributed implementation

The routing phase of the VMIMOCR algorithm, which is responsible for finding a route from the source node to the sink node, could be implemented using one of the previously published routing protocols. For the purpose of performance evaluation, we chose to implement this phase using the Ad hoc On-demand Distance-Vector routing protocol (AODV)with some modifications and with the links’transmissions energy used as the virtual link cost. The VMIMOCR algorithm includes three parts: the source node behavior shown in Algorithm 1,

The behavior of a virtual intermediate node when receiving RREQ and RREP.5.4.1.1 Source node behavior

Algorithm 1 shows the behavior of the source node in the VMIMOCR algorithm. For a new arriving flow, when a sourcesintends to send packets to a destinationd,sfirst checks its routing table to see whether it has a valid path to a destination noded. If so,sbegins to send packets to the next hop towards the destination; otherwise, it searches for the path by broadcasting a RREQ message to its one-hop virtual neighbors.

5.4.1.2 Virtual Intermediate Node Behavior When Receiving RREQ

As shown in Algorithm 2, when a virtual intermediate nodex’in the network receives an RREQ from virtual nodey’, virtual intermediate nodex’can obtain virtual link costLy’andLy’x’. The current virtual link cost from the sourcesto virtual nodex’is denoted ascLx’=Ly’+Ly’x’. The recorded virtual link cost fromstox’is denoted asLx’’.

If the virtual intermediate nodex’contains the destination noded, it can wait for some interval of time, then choose the path which has the Minimum virtual link cost from all the RREQ received within the interval. Then, it responds by sending an RREP message (including each hop links) back to the source.

Otherwise, virtual nodex’updates the virtual link cost of the path segment from the sourcesto nodex’, that isLx’=cLx’. It then performs the following operations: it first deletes the link information about other neighbors from the received RREQ; it then calculates and inserts the routing metric of all its outgoing links into the RREQ message, and rebroadcasts the message.

5.4.1.2 Virtual Intermediate Node Behavior When Receiving RREP

Once receiving an RREP message, if the virtual node is a hop sender in the selected path,the node will notify its selected relay node through a Hello message to synchronize their transmission of the data packet. Then the node will send the RREP to the upstream node in the path.

After receiving the RREP message, the source forwards its data packets along the selected path to the destination.

VI. SIMULATION RESULTS

6.1 Simulation Configuration

In this section, we firstly discuss X’s impact on VMIMOCR, and then compare network lifetime of VMIMOCR with other three categories of algorithms.

The first category is based on traditional routing method, including MTE, FA. MTE is used for minimizing total energy, and FA is used for maximizing network lifetime.

The second category is based on VMISO,including CSP and FACR. CSP is used for minimizing total energy, and FACR is used for maximizing network lifetime.

The third category is based on VMIMO,including CwR+. CwR+ is the modified algorithm of CwR. It selects main routes by usingFA and employs cooperative relay node via CwR.

Algorithm 1 Behavior of Source Node s

Algorithm 2 Behavior of an intermediate node x’ when receiving RREQ

In order to describe the simulation result,we classified algorithms into two groups according to different objectives. The first group aims to minimize energy consumption, including MTE, CSP and CwR+. The second group aims to maximize network lifetime, including FA and FACR.

We distributeNnode randomly in the network. The power loss factorfrom nodeito nodetis inversely proportional to the square of distance betweeniandt. The lon-gest communication range under transmission powerPintraandPinteris 40, 100 respectively. It is assumed that nodeineeds consumeei=(D/400)2energy to transmit one unit data,andDrepresents distance between sender and receiver. The initial energy of each node is 1. The source and destination pair is chosen randomly to transmit data. After completing transmission, the source and destination are selected again until one node exhausts its energy. We compare the network lifetime of VMIMOCR with other algorithms under different node density and network size.

Fig. 10 Network lifetime with different X

Fig. 11 Network lifetime with different node density for group one

6.2 The impact of parameter X

The parameter X defines the relationship between the ratio of initial energy to remaining energy and transmission power, and affects the algorithm’s performance. Figure 10 shows the lifetime network of VMIMOCR under different node density and X. The value of X is taken from 0 to 5. Nodes are randomly distributed in a 320*320 areas. The number of nodes is 35, 45 and 55. The vertical axis is network lifetime, that is, the number iteration before network dead. The horizontal axis is the value of X.

The result shows that the network lifetime improves with the increasing node density.And this is similar to traditional routing algorithm. When X = 0, VMIMOCR doesn’t consider initial energy and remaining energy,and the performance is worse than the performance with X ＞0. When X ＞1, network lifetime increase evidently and tends to stabilize.The change character is almost same under different node density, and fluctuation range is within 5%. We set X=1 in the following simulation.

6.3 Node density

We randomly distribute 25, 35, 45, 55 and 65 nodes respectively in a 320*320 areas. Figure 11 and 12 shows the network lifetime under different node density. The vertical axis is network lifetime, and the horizontal axis is node denity.

Figure 11 shows that compared with MTE,CSP and CwR+, VMIMOCR can improve network lifetime 315%, 101% and 126% respectively in the network with 45 nodes, and 348%, 142% and 109% respectively in the 65 nodes network. Because MTE, CSP and CwR+ concern the minimum total energy consumption, and may cause some nodes exhaust their energy very oon.

Figure 12 shows the result compared with FA and FACR. From Figure 12, we can con-clude that when the number of nodes is larger than 35, VMIMOCR has the longest network lifetime. Compared with FA and FACR, the network lifetime of VMIMOCR can improve 83% and 41% respectively in the network with 45 nodes, and 69% and 37% respectively in the network with 65 nodes. Besides, when the node density is sparse, the network lifetime is worse than that of algorithms based on MISO,such as CSP and FACR.

Table 1 counts the number of members in the virtual nodes. When the number of nodes is 25, there are 16 nodes that employ no cooperative relay nodes, and only 1 node employ 2 cooperative relay nodes. The result shows that when the node density is sparse (N=25), it’s hard for master nodes to employ cooperative relay nodes for transmission, resulting in the performance decrease.

6.4 Network size

We compare algorithm’s performance under different network size. And 45 nodes are randomly distributed in 400*400, 350*350 and 300*300 respectively. Figure 13 shows the network lifetime of six algorithms. The vertical axis represents the network lifetime,and the horizontal axis represents the six algorithms. When network connectivity is small(400*400), it’s hard for VMIMOCR to employ cooperative relay nodes, and its network lifetime is shorter than that of FACR and FA.In the medium network size (350*350), VMIMOCR can extend network lifetime 408%,92%, 216%, 44% and 58% respectively, compared with MTE, FA, CSP, FACR and CwR+.In the high node density network (300*300),VMIMOCR can improve network lifetime 365%, 90%, 108%, 50% and 10% respectively, compared with MTE,FA,CSP,FACR, and CwR+.

6.5 Disadvantage

Fig. 12 Network lifetime with different node density for group two

Fig. 13 Network lifetime with different network size

Table I The number of cooperative relay nodes of VMIMO with different network size

From the above simulation results, we found out that VMIMOCR algorithm make the network to obtain close-to-optimal network lifetime. However, this may not always be the case. Actually, considering the fact that we can’t predict the state information about future flows, the simulation results are too good to believe. In the following, we give an example that shows that the performance of the algorithm depends on the state information about future flows. Consider a network in Fig. 14 where virtual nodesa,bandchave four units of energy. It requires one unit of energy per packet to cross each link. The reception energy consumption is assumed to be zero. If eight packets are generated at virtual nodeS1before the four packets are generated at virtual nodeS2, the algorithm finds the routes as shown in Fig. 14(a) which achieves the optimal network lifetime of 12 time units. However, if four packets at virtual nodeS2are generated before the eight packets virtual nodeS1, the algorithm finds the routes as shown in Fig. 14(b) which achieves the network lifetime of 10 time units.

Compared to traditional routing, the cooperative routing has a higher energy efficiency,at the expense of more complexity and signaling overhead. M Elhawary analyzes the overhead of the control packets in CAN and CwR protocol [19], VMIMOCR algorithm is similar to CwR protocol in the routing phase.Different from CwR algorithm, the HELLO message of the VMIMOCR algorithm has been modified in order to node virtualization.The HELLO message carries the additional information: remaining energy and neighbors’link costs. Moreover, VMIMOCR algorithm needs additional vHELLO message to maintain the virtual node status information.

F ig. 14 Network lifetime with different network size

VII. CONCLUSIONS

By considering initial energy, remaining energy and channel state, this paper proposes a solution of cooperative relay node selection based on VMIMO cooperative communication model, power allocation, cooperative path finding, and designs a cooperative algorithm-VMIMOCR. According to neighbors’state information, the algorithm chooses optimal cooperative node set, balance the energy cost among senders, and determines final forwarding paths based on virtual link cost. The proposed algorithm fully exploits the advantage of VMIMO cooperative communication.The simulation result shows that VMIMOCR can extend network lifetime from 37% to 348% in the medium network size.

ACKNOWLEDGEMENTS

This work was supported by the National Basic Research Program of China (973 program)(Grant No. 2012CB315805) and the National Natural Science Foundation of China (Grant No. 61472130 and 61572184).

[1] A. Nosratinia, T.E. Hunter, A. Hedayat, “Cooperative communication in wireless networks”,IEEE Communications Magazinevol.42, no.10, pp 74-80, Oct, 2004.

[2] Sendonaris A, Erkip E, Aazhang B, “User cooperation diversity. Part I. System description”,IEEE Transactions on Communications, vol.51, no.11,pp 1927-1938, Nov, 2003.

[3] Sendonaris A, Erkip E, Aazhang B, “User cooperation diversity. Part II. Implementation aspects and performance analysis”,IEEE Transactions on Communications, vol.51, no.11, pp 1939-1948,Nov, 2003.

[4] Zhang J, Zhang Q, “Cooperative Routing in Multi-Source Multi-Destination Multi-Hop Wireless Networks”,INFOCOM 2008, The 27th Conference on Computer Communications, IEEE,pp 2369-2377, 2008.

[5] Sharma S, Yi Shi, Hou Y T, et al, “Cooperative Communications in Multi-hop Wireless Networks: Joint Flow Routing and Relay Node Assignment”,INFOCOM, 2010 Proceedings IEEE,IEEE, pp 1-9, 2010.

[6] Zhang Jin, Zhang Qian, “Contention-Aware Cooperative Routing in Wireless Mesh Networks”,IEEE International Conference on Communications 2009 (ICC ‘09), IEEE, pp 1-5, 2009.

[7] Ong L, Motani M, “Optimal Routing for Decode-Forward in Cooperative Wireless Networks”,IEEE Transactions on Communications,vol.58, no.8, pp 2345-2355, August, 2010.

[8] Yao X, Yang G, Wei C, et al, “Location-Aware cooperative routing in multihop wireless networks”IEEE Wireless Communications and Networking Conference 2011 (WCNC ‘11), IEEE, pp 761-766, 2011.

[9] Syue S J, Wang Chin-Liang, Aguilar T, et al, “Cooperative Geographic Routing with Radio Coverage Extension for SER-Constrained Wireless Relay Networks”,IEEE Journal on Selected Areas in Communications, vol.30, no.2, pp 271-279,February, 2012.

[10] Sheng Min, Li Jiandong, Li Hongyan, et al, “Small World Based Cooperative Routing Protocol for Large Scale Wireless Ad Hoc Networks”,IEEE International Conference on Communications 2011 (ICC ‘2011),IEEE, pp 1-5, 2011.

[11] Hong Qiao, Dafang Zhang, Kun Xie, et al, “Distributed fair cooperative routing in multi-gates wireless mesh network”,Journal on Communications, vol.36, no.2, pp 175-185, February,2015. ( in Chinese )

[12] Xie K, Wang X, Liu X, et al, “Interference-Aware Cooperative Communication in Multi-radio Multi-channel Wireless Networks”,IEEE Transactions on Computers, vol.65, no.5, pp 1528-1542,May, 2016.

[13] Khandani A E, Abounadi J, Modiano E, et al,“Cooperative routing in static wireless networks”IEEE Transactions on Communications,vol.55, no.11, pp 1-23, Nov, 2007.

[14] Li F, Wu K, Lippman A, “Energy-efficient cooperative routing in multi-hop wireless ad hoc networks”IEEE International Performance, Computing, and Communications Conference, IEEE,pp 215-222, 2006.

[15] Ibrahim A, Zhu H, Liu K J R, “Distributed energy-efficient cooperative routing in wireless networks”IEEE Trans Wireless Commun, vol.7,no.10, pp 3930-3941, October, 2008.

[16] Lang Y, Wubben D, Dekorsy A, “Optimal Power Routing for End-to-end Outage Restricted Distributed MIMO Multi-hop Networks”,Communications (ICC), 2011 IEEE International Conference on,IEEE, pp 1 – 5, 2011.

[17] Siam M. Z., Krunz M., Younis O, “Energy-efficient clustering/routing for cooperative mimo operation in sensor networks”,INFOCOM 2009, IEEE,pp 621-629, 2009.

[18] Krunz M, Siam M Z, Nguyen D N, “Clustering and power management for virtual MIMO communications in wireless sensor networks”,Ad Hoc Networks, vol.11, no.5, pp 1571-1587, July,2013.

[19] Elhawary M, Haas Z J, “Energy-Efficient Protocol for Cooperative Networks”,IEEE/ACM Transactions on Networking, vol.19, no.2, pp 561-574,April, 2011.

[20] Mansourkiaie F, Ahmed M H, “Joint Cooperative Routing and Power Allocation for Collision Minimization in Wireless Sensor Networks With Multiple Flows”,Wireless Communications Letters IEEE, vol.4, no.1, pp 6-9, Feb, 2015.

[21] Wei Y, Teng Y, Li W, et al, “Energy Saving Cooperative Communication over Fading Channels with Relay Selection and Power Control”,China Communications, vol.9, no.6, pp 6-9, 2012.

[22] Ding J, Liu D, Wu H, “A Cooperative MIMO Transmission Scheme for Cluster-based Wireless Sensor Networks”,China Communications,vol.7, no.5, pp 14-22, 2010.

[23] Pandana C, Siriwongpairat W P, Himsoon T, et al, “Distributed cooperative routing algorithms for maximizing network lifetime”,Wireless Communications and Networking Conference, 2006,IEEE, pp 451-456, September, 2006

[24] Zhang J, Zhang D, Xie K, et al, “A Cooperative Routing Algorithm for Maximizing Network Lifetime”,Advances in Wireless Sensor Networks,Springer, pp 665-675, 2013.

[25] Dewangan K, Bhattacharjee S, “Lifetime maximizing cooperative energy efficient broadcast tree in multi hop wireless networks”,Advance Computing Conference (IACC), 2014 IEEE International, IEEE, pp 318-322, 2014.

[26] Pei T, Xie D, Li Z, et al, “A Heterogeneous-aware Cooperative MIMO Transmission Scheme in WSN”,Journal of software, vol.8, no.3, pp 639-644, March, 2013.

[27] Bin L I, Wang W J, Yin Q Y, et al, “An energy-efficient geographic routing based on cooperative transmission in wireless sensor networks”,Science China Information Sciences, vol.56, no.7,pp 1-10, February, 2013.

[28] Chang J H, Tassiulas L, “Maximum lifetime routing in wireless sensor networks”,IEEE/ACM Transactions on Networking, vol.12, no.4, pp 609-619, Aug, 2004.

[29] Toh C K, “Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks”,IEEE Communications Magazine, vol.39, no.6, pp 138- 147, Jun, 2001.

[30] Kleider J E, Maalouli G, Ma X, “Timing Synchronization in Distributed Mobile MISO Rayleigh Fading Channels”,Military Communications Conference, 2007, IEEE, pp 1-7, 2007.

[31] Xie K, Wang X, Wen J, et al, “Cooperative routing with relay assignment in multiradio multihop wireless networks”,IEEE/ACM Transactionson Networking, vol.24, no.2, pp 1-14, March,2015.

[32] Xie K, Cao J, Wang X, et al, “Optimal Resource Allocation for Reliable and Energy Efficient Cooperative Communications”,IEEE Transactions on Wireless Communications, vol.12, no.10, pp 4994-5007, October, 2013.

[33] Xie K, Cao J N, Wen J G, “Optimal Relay Assignment and Power Allocation for Cooperative Communications”,Journal of Computer Science and Technology, vol.28, no.2, pp 343-356,March, 2013.