ABSTRACT

With the advent of sensor nodes with higher communication and sensing capabilities, the challenge arises in forming a data gathering network to maximize the network capacity. The channel sharing for higher data transmission leads to interfering problems. The effects of interferences become increasingly important when simultaneous transmissions are done in order to increase wireless network capacity. In such cases, achieving a high throughput and low delay is difficult. We propose a new method that uses interference alignment (IA) technique to mitigate interference effects in Wireless Sensor Networks (WSNs). In IA technique, multiple transmitters jointly encode their signals to intended receivers such that interfering signals are separated and eliminated. Simulation results demonstrate that compared to TDMA algorithms, the proposed method significantly increases the performance of the network delay and throughput by reducing the delay and increasing throughput.

1. Introduction

A WSN consists of a group of sensor nodes, which are deployed in a region of interest. The sensor nodes sense and gather information from the environment and send their data to the destination node [1]. The sensor nodes cooperate to accomplish a common task, such as battle field surveillance and environment monitoring [2]. All the sensor nodes use a radio channel and share the same medium for transmission. During the transmission of a node, the other nodes which are in conflict with the transmitter node cannot transmit. There are two forms of conflicts: primary and secondary conflicts. The primary conflict happens when a node receives more than one transmission or transmits and receives in one time slot. The secondary conflict happens when a receiver R is tuned to a particular transmitter T within the range of other transmitters whose transmissions are not for R and interfere with the transmissions of T [3]. The conflict causes packet loss, packet retransmission, delay increment, and throughput decrement [4]. The TDMA is a good solution to avoid conflicts. In the TDMA, each time slot is allocated to some of sensor nodes which are not in conflict with each other. For reducing the interference effect and decreasing the transmission delay, in [5] using the graph coloring strategy, two centralized TDMA scheduling algorithms are developed, one node-based scheduling and the other level-based scheduling. In the node-based scheduling, scheduling is obtained based on coloring of the original network. The nodes of the color corresponding to each slot with at least one packet are chosen first and additional nodes are added afterwards. In the levelbased scheduling, the original network is transformed to a linear network where each node corresponds to a level in the original network. The scheduling of the original network is then obtained based on coloring of the linear network. This scheduling algorithm schedules a nonconflicting set of nodes corresponding to levels of each color for the current slot and then schedules additional nodes, if possible. In TDMA, the nodes which interfere with each other are not permitted to transmit simultaneously. Thus, the transmissions delay of packets to Base Station (BS) increases and the throughput decreases. In this paper, a novel method is proposed for WSNs that use interference alignment technique (IA). In the IA multiple nodes jointly encode their signals to their intended receivers such that interfering signals are separated and eliminated in each receiver. Thus, by applying the IA technique to WSN, the nodes which are within the interference range of each other and have different receivers, can transmit simultaneously. In proposed method, multiple sets of nodes are selected to use IA technique and the nodes of each set can transmit by using IA simultaneously. However the nodes of each setare in conflict with each other, the proposed method provides simultaneous transmissions. So, the centralized scheduling in the proposed method differs from network scheduling in conditions that the network doesn’t use IA technique. The network scheduling is done based on a graph coloring strategy.

The rest of the paper is organized as follow. Section 2 explains the model network. Section 3 presents the IA technique. In Section 4, the IA technique in WSNs is proposed. Simulation results are given in Section 5 and Section 6 concludes the paper.

2. Model Network

We consider a static WSN in which sensor nodes periodically collect information about the environment and send their data to the BS via multi hop transmission. We model the WSN network by a graph where is the set of nodes and is the set of wireless links among nodes. Each node has a transmission radius of and an interference radius of. If the node wants to receive the message from correctly, their distance must be less than . The signal of is interfered with the signal of , if their distance is less than and is not the intended receiver. and are not necessarily the same. Typically is smaller than and in practice [6]. The conflict graph is a graph in which every node represents an edge in the original graph and two nodes are connected in if their corresponding edges are in conflict with each other in the original graph. A node is at level n if it is located at the distance of n hops from the BS [5]. The protocol model in [7] is selected for the interference in which a packet is correctly received if no other nodes transmit simultaneously within the receiver interference range. This model enables the use of graph coloringbased scheduling algorithms [2].

3. Interference Alignment

The research on achieving simultaneous transmissions and receptions has a long literature. In the [8], [9], the interference alignment [8] and zero forcing [9] methods are addressed in which, multiple transmitters jointly encode and send their signals to intended receivers such that interfering signals are separated and eliminated [10]. In the IA in transmitters aligning matrices are applied to send the signals such that interfering signals at each receiver lie in a subspace which is linearly independent of desired signal subspace [8]. Then, the zero forcing filter is applied to the received signal to eliminate interference signals and retain the desired signal. Consider a K-user interference channel consists of K transceivers pairs in which the transmitters to send their signals to the receivers to. Each transmitter and receiver is equipped with single antenna. As shown in Figure 1,

each receiver only decodes the signal of its own transmitter and the signals of other transmitters are considered as interference. The desired and interference signals are shown by solid lines and dashed lines, respectively. It is assumed that the full channel state information is available at every transmitter and receiver. The signal received by the i-th receiver can be expressed as

(1)

where represents the signal of transmitter i, is the aligning matrix for the i-th user, represents the channel matrix from transmitter j to receiver i and is the additive white Gaussian noise with zero mean and unit variance. For perfect aligning of interferences of Transmitters 2 to K in Receiver 1, we should have

(2)

and in Receiver 2,

(3)

and in Receiver i

(4)

The Equations (2)-(4) can be shown as

(5)

By solving (5), aligning matrices are obtained and by aligning interference signals in each receiver, the desired signal subspace and interference signals subspace will be linearly independent. By applying the zero forcing filter to at each receiver, we get for.

(6)

where

(7)

Thus,

(8)

Figure 2 shows the IA solution for a 3-user interference channel. The desired and interference signals are presented by solid lines and dashed lines, respectively. The receiver of each user only needs to decode the signal of its own transmitter. By applying aligning matrices in transmitters, interference signals received at each receiver align in a one-dimensional subspace and are linearly independent of the desired signal subspace.

4. Proposed Method

We apply the IA technique to WSNs. Applying the IA to WSN is performed in three parts. First, we select those nodes which make use of the IA technique for transmission. In the second part, for network scheduling we color the conflict graph using a graph coloring algorithm. In the third part, network scheduling is obtained based on graph coloring. We assume the number of sensor nodes is N, the nodes which are using the IA is and the restare in the set. The number of an arbitrary set members such as is represented by and parent of an arbitrary node such as is represented by.

(9)

4.1. Node Selection for Interference Alignment

In a WSN a single node can both gather and forward the packets. The nodes transmitting more packets, experience more strict congestion, which makes delay in packet transition to the BS. For a better performance, the IA technique is applied to the nodes with strict congestion.

Node selection has three stages. In the first stage, the forward degree for each node is computed. Forward degree for each node is equal to the number of nodes which forward their packets through that node over the routing tree. Figure 3 illustrates a network with the forward degree of nodes.

Then, nodes are ordered in a decreasing degree of forward. Assuming each node sends at least one packet at each transmission cycle, in the second stage, we choose the nodes with a high forward degree (nodes with degree more than 10 times of the minimum degree). In the third stage, we choose the sets of nodes among the selected nodes in the second stage which compose a multi-user interference channel with their parents. It means that the nodes of each set should be within the interference range of other set nodes and cannot transmit simultaneously without IA. Thus, an arbitrary set such as that composes a K-user interference channel, should have the following conditions:

1) Any two nodes of each set should have different parents.

(10)

2) The parent (receiver) of each node (transmitter) should be within the interference range of other set nodes (other transmitters).

(11)

where represents the distance between node i and j.

3) Each node with its parent cannot be in the same set.

(12)

For example, Figure 4 displays a WSN with 1000 nodes deployed in a circular area and the BS is located in the center of the circle. Figures 5 and 6 display selected nodes in the 2nd and 3rd stages, respectively. In this example, the number of sets are using the IA is six. The nodes of each set are shown in the same color.

4.2. Coloring of Network Graph

For transmission scheduling, first, we color the

using a graph coloring algorithm. For this purpose each two nodes with different colors cannot transmit simultaneously [5]. Coloring the network has two steps. In the first step, we color nodes using IA for transmission, i.e. nodes member of. In the second step, we color other nodes in the network, i.e. nodes member of. To assign color to the nodes of, weform the sets graph with. The node corresponds to all nodes at set i and two nodes and are connected if there is an edge between a node at set i and any node at set j in the conflict graph of the original network. Thus, we have

(13)

Then, the conflict degree for each node in the is obtained. The degree conflict of each node in the is equal to the number of connected edges. Then, the nodes in the are ordered in a decreasing degree of conflict and priority of coloring is given to the nodes with a more conflict degree. In coloring the, every two nodes conflict with each other have different colors. Thus, if two sets conflict with each other have different colors. Since all members of a set can transmit simultaneously, they have the same color. Then, the conflict degree for each node in the is obtained. The degree conflict of each node in the is equal to the number of connected edges. Then, the nodes in the are ordered in a decreasing degree of conflict and priority of coloring is given to the nodes with a more conflict degree. In coloring the, every two nodes conflict with each other have different colors. Thus, if two sets conflict with each other have different colors. Since all members of a set can transmit simultaneously, they have the same color.

For assigning color to the nodes, the degree conflict of each node in the is obtained. Then, nodes are ordered in a decreasing degree of conflict and the priority of color assignment is given to the nodes with a more conflict degree. As some colors were already assigned to the nodes, for assigning color to nodes the, conflict of each new node is examined with all nodes corresponding to each color. If there is no conflict, the color is assigned to the new node; otherwise, other colors should be examined.

Finally, if any color among available colors is not assigned to the new node, a new color should be assigned. The coloring algorithm is given in Figure 7.

4.3. Scheduling Network

The scheduling algorithm assigns one or more time slots to each node in the network for conflict-free communication such that the delay in data collection is minimized. The network scheduling is obtained based on graph coloring. A super slot in our scheduling algorithm is a set of sequential time slots such that each node having one packet or more at the beginning of the super slot sends at least one packet throughout the superslot. All of the nodes allocated to the same color can send at a time slot. The maximum number of slots in a superslot is the total number of colors utilized for coloring the network. After determining the nodes corresponding to the current time slot, as long as the resulting set is non-conflicting extra nodes allocated to other colors are added.

The proposed method is practical for actual static WSNs, which in the locations of nodes are fixed, because the node selection part of the proposed method is

done once such that this part is not required for each data collection cycle. In other words, the node selection part loads no additional delay during the transmission. Other two parts of the proposed method have similar computational complexity to the node-based and level-based scheduling algorithms.

5. Simulation Results

For evaluation of the proposed method, we use two metrics; the delay and throughput. The delay is the time duration in which all packets generated by all nodes reach the BS. The throughput is the average rate of successful data delivery over the channel and it is measured in data packets per time slot. In simulations, the WSN consists of 1000 sensor nodes randomly distributed within a circular area with radius of 100 units. The BS is located in the center of the circular area. The density of sensor nodes within the radius is and between the radius and 100 is. We use Dijkstra algorithm as shortest path routing to determine the routing tree rooted at the BS. The results presented here are the average performance of 100 different network realizations. The results of simulation are compared to two TDMA scheduling algorithms, one node-based and the other level-based [5]. Figures 8 and 9 respectively display the delay and average throughput of the proposed method in comparison with the TDMA scheduling algorithms versus for, respectively. As the simulations show, by using proposed method, the delay greatly reduces and throughput significantly increases.

This happens since in TDMA without using IA, the nodes which are within the interference range of each other cannot transmit simultaneously causing the delay to increase and throughput to decrease. In contrast, while IA is used, these nodes can transmit simultaneously. Hence, the number of concurrent transmissions increases leading the delay to decrease and throughput to increase. Also, the simulation results demonstrate that the performance of the proposed method depends on thenetwork topology. Figure 10 shows the percentage of performance improvement (PPI) of the proposed method with respect to node-based and level-based algorithms versus

. In Figure 10, by increasing the ratio, the PPI increases to a certain value and afterwards decreases. Therefore, for, the proposed method presents a good PPI in topologies with the medium ratios and a lower PPI in the topologies with low and high ratios. These changes are due to dependency of the proposed method performance on two factors:

1) Interference degrees of selected nodes in 2nd stage: the interference degree for each node is the number of nodes interfere that with it. With increasing, the number of nodes increases causing improvement in proposed method performance because the proportion of packets transmitted by nodes to that of nodes increases.

2) The difference between forward degrees of nodes and: With increasing, the performance of the proposed method improves because the proportion of packets transmitted by nodes to that of nodes increases.

With increasing, increases while decreases. Up to a certain amount of, influence of increment is predominant and afterwards influence of decrement becomes predominant.

Figures 11-13 show the impact of interference radius on performance of these methods. These figures show the delay of the methods versus for three ratios of as follows:

· , represents a topology in which the density of packets is higher at the upper levels of the routing tree.

· , represents a topology in which the density of packets is equal throughout the network.

· , represents a topology in which the density of packets is higher at the lower levels of the routing tree.

Results show that with increasing the ratio, the delay is increased, because the number of the nodes

which interfere with each other increases and the number of concurrent transmissions decreases resulting in a decreased transmission rate and an increased delay. Figure 14 shows the PPI of the proposedmethod with respect to the node-based algorithm versus. In Figure 14, by increasing ratio for the topologies with the medium or high ratios, the PPI increases while for the topologies with low ratios, the PPI increases to a certain value and afterwards decreases. Figures 15-17 display the average throughput of these methods versus for three values of, respectively. Simulation results show that the proposed method performs better in topologies with the same ratio of and. This happens since in topologies with the medium ratio, both and is high while in topologies with low ratio, is low and in topologies with high ratio, is low.

6. Conclusion

We applied the IA technique to WSNs to reduce interference effects. In this way, multiple transmitters jointly encode their signals to intended receivers such that interfering signals are separated and eliminated at each

receiver. By applying the proposed methodto WSNs, delay and throughput performances significantly improve. The performance of the proposed method depends on the network topology. Compared to the topologies with low and high ratios, in the topologies with the medium ratios, the percentage of performance improvement in the proposed algorithm is more.

REFERENCES