Minimizing the maximum sender interference by deploying additional nodes in a wireless sensor network

Pushparaj Shetty D., M. Prasanna Lakshmi


Interference is one of the major challenges faced by the communication networks. Since the interference leads to packet loss, packet collision and data re-transmission, higher the interference, higher is the energy consumption. Several algorithms were proposed for reducing the interference in a Wireless sensor network (WSN). By deploying additional nodes at an appropriate position in a WSN, it is possible to reduce the interference. We propose an algorithm in which, the main objective is to reduce the maximum Sender interference by deploying the additional nodes in the network, while connectivity of the network is preserved. We use the properties of Gabriel graph to achieve the reduction in interference. We present the simulation results which show the number of additional nodes to be deployed. The comparison of the maximum Sender interference obtained by the proposed algorithm with that of the Euclidean minimum spanning tree (MST) of the given network is presented through simulation. We show that the additional number of nodes required for deployment has an upper bound of n/2, where n is the number of nodes. We also compute the average reduction in Sender interference of the network for a various number of nodes.  


wireless sensor network, sender interference, minimum spanning tree, graph algorithms, deployment of nodes

Full Text:




P. Agrawal and G.K. Das, Improved interference in wireless sensor networks. Distributed Computing and Internet Technology, ICDCIT Proceedings, (2013), 92–102.

I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, Wireless sensor networks: a survey, Computer networks 38 (4) (2002), 393–422.

D. Bilo` and G. Proietti, On the complexity of minimizing interference in ad-hoc and sensor networks. Theor. Comput. Sci., 402 (1) (2008), 43–55.

X.Cheng, B.Narahari, R.Simha, M.X. Cheng, and D.Liu,Strong minimum energy topology in wireless sensor networks: NP-completeness and heuristics. IEEE Trans. Mob. Comput., 2 (3) (2003), 248–256.

K.R. Gabriel and R.R. Sokal, A new statistical approach to geographic variation analysis, Systematic Biology, 18 (3) (1969), 259–278.

R. Hayward, D. Rappaport, and R. Wenger, Some extremal results on circles containing points. Discrete & Computational Geometry, 4 (3) (1989), 253–258.

E. Langetepe, A. Lenerz, and B. Bru ̈ggemann (2014). Strategic deployment in graphs. Informatica (Slovenia), 39 (3) (2015), 237–247.

X. Liu and P. Mohapatra, Placement of sensor nodes in wireless sensor networks. (2004)

D.W. Matula and R.R. Sokal, Properties of gabriel graphs relevant to geographic variation research and the clustering of points in the plane. Geographical analysis, 12 (3) (1980), 205–222.

R. Niati, N. Yazdani, and M. Nourani, Deployment of spare nodes in wireless sensor net- works. Wireless and Optical Communications Networks, IFIP Conference proceedings, IEEE, (2006), 5-pp.

B. Panda and D.P. Shetty, Strong minimum interference topology for wireless sensor networks, Advanced Computing, Networking and Security, Springer, 7135 (2011), 366–374.

S. Rangwala, R. Gummadi, R. Govindan, and K. Psounis, Interference aware fair rate control in wireless sensor networks, ACM SIGCOMM Conference Proceedings, 36 (4) (2006), 63–74.

D.P. Shetty, M.P. Lakshmi, Algorithms for minimizing the receiver interference in a wireless sensor network. DISCOVER conference proceedings, IEEE, (2016), 113–118.

D.B. West, Introduction to graph theory, Pearson Education (Singapore) Pte.Ltd., Second Edition, 2001.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats