Share / Export Citation / Email / Print / Text size:

International Journal on Smart Sensing and Intelligent Systems

Professor Subhas Chandra Mukhopadhyay

Exeley Inc. (New York)

Subject: Computational Science & Engineering, Engineering, Electrical & Electronic


eISSN: 1178-5608



VOLUME 7 , ISSUE 2 (June 2014) > List of articles


Anindya Nag * / Rajarshi Roy *

Keywords : Yao-graph, Yao-Yao graph, Theta-graph, Spanner, Unit disk graph, Power, Degree bound.

Citation Information : International Journal on Smart Sensing and Intelligent Systems. Volume 7, Issue 2, Pages 740-761, DOI: https://doi.org/10.21307/ijssis-2017-679

License : (CC BY-NC-ND 4.0)

Received Date : 28-March-2014 / Accepted: 10-May-2014 / Published Online: 27-December-2017



The advent of wireless communication and networking in the last two decades has led to the need of modification in the regular graphs used as spanners. The spanner is a sub graph of the original graph which connects the essential nodes for transmission of the message. For this purpose the Omni directional antennas are usually used and the “spanner-graph” performance metric is a constant multiplied by the same of the original graph. This constant is known as the “stretch factor”. One of the most common attribute for wireless communication is the energy required for faithful transmission of a message between two nodes. But the Omni directional antennas lead to interference and wastage of bandwidth and energy. The nodes of wireless communication are however neither always static nor equipped with any infrastructure. Rather the same might as well be ad-hoc and mobile. Another well used notion is that of the unit disk graph (UDG), where a node can communicate only if the other nodes are within the disk of unit radius. However the graph being dynamic in nature, the nodes do not have fixed transmission radii and the same changes according to the power requirement of transmission. This work of ours mainly deals with the different graphs being used as spanners. It explains a few algorithms described in other papers which it reviewed. The associated algorithms are related to Yao graph. This graph and its modifications are discussed and it is explained how they could be used energy efficiently. The Yao-Yao graph for example can be used as a spanner for certain specific values of stretch factors.

Content not available PDF Share



[1] Anthony Ephremides, Bruce Hajek, “Information theory and communication networks: an unconsummated union”, IEEE Transactions on Information Theory, Vol. 44, No. 6, pp. 2416-2434, Oct 1998.
[2] Sha Hua, Hang Liu, Mingquan Wu, S.S. Panwar, “Exploiting MIMO antennas in cooperative cognitive radio networks”, IEEE INFOCOM 2011, 10-15 April, 2011, pp. 2714-2722, Shanghai, Chaina. DOI: 10.1109/INFCOM.2011.5935102.
[3] C.X. Wang, X. Hong, X. Ge, X. Cheng, G. Zhang, J. Thompson, “Cooperative MIMO channel models: A survey”, IEEE Communications Magazine, Vol. 48, No. 2, pp. 80-87, Feb 2010. DOI: 10.1109/MCOM.2010.54.02668.
[4] Y.C. Liang, K.C. Chen, G.Y. Li, P. Mahonen, “Cognitive radio networking and communications: an overview”, IEEE Transactions on Vehicular Technology, Vol. 60, No. 7, pp. 3386-3407, Sept 2011. DOI: 10.1109/TVT.2011.2158673.
[5] K.J. Ray Liu, Ahmed K. Sadek, Weifeng Su, Andres Kwasinski, “Cooperative Communications and Networking”, Cambridge University Press, 2009. ISDN: 978-0-521-89513-2 hardback.
[6] R. Swaminathan, Rajarshi Roy, M.D. Selvaraj, “Performance analysis of triple correlated selection combining for cooperative diversity systems”, IEEE ICC 2013, Budapest Hungary, pp. 5483-5488.
[7] R. Swaminathan, M.D. Selvaraj, Rajarshi Roy, “Exact Error Analysis of MPAM Signaling for a Cooperative Diversity System with Correlated Links Using Paired Error Approach”, IEEE Communication Letters, Vol. 18, No. 2, pp. 273-276, Feb 2014.
[8] Soumendra Nath Datta, Saswat Chakrabarti, Rajarshi Roy, “Comprehensive Error Analysis of Multi-Antenna Decode-and-Forward Relay in Fading Channels”, IEEE Communication Letters, Vol. 16, No. 1, pp. 47-49, 2012.
[9] Soumendra Nath Datta, Saswat Chakrabarti, Rajarshi Roy, “Comprehensive error performance analysis of distributed selection combining with multi-antenna amplify-and-forward relay over Nakagami-m fading channels”, IET Electronics Letters, Vol. 46, No. 22, pp. 1523-1525, 2010.
[10] M.V. Kumar, R. Swaminathan, R.Roy, “Green cooperative communication techniques for intelligent transportation systems”, IEEE International Conference on Signal Processing, Computing and Control, Wakhnaghat, Shimla, HP, India, 26-28 Sept., 2013, pp. 1-5. DOI: 10.1109/ISPCC.2013.6663432.
[11] Acharya, T., Chattopadhyay, S. and Roy, R. ‘Maximum lifetime broadcasting in cooperative multi-hop wireless ad hoc networks’, Int. J. Ad Hoc and Ubiquitous Computing, Vol. 6, No. 1, pp. 10–23, 2010.
[12] H. Zhang, N.B. Mehta, A.F. Molisch, Jin Zhang, Dai Huaiyu, “Asynchronous interference mitigation in cooperative base station systems”, Vol. 7, No. 1 , pp. 155-165, IEEE Transactions on Wireless Communications, Jan 2008.
[13] L.Lai, H. El Gammal, “On cooperation in energy efficient wireless networks”, IEEE Transactions on Wireless Communication, Vol. 7, No. 5, pp. 1868-1878, May 2008.
[14] Chun Nie, Pei Liu, Thanasis Korakis, Elza Erkip, Shivendra Panwar, “CoopMAX: A Cooperative MAC with Randomized Distributed Space-Time Coding for an IEEE 802.16 Network”, IEEE ICC 2009, IEEE International Conference on Communications, pp. 5212-5217.
[15] Peijian Ju, Wei Song, Dizhi Zhou, “Survey on cooperative medium access control protocols”, IET Communications 2013, Vol. 7, No. 9, pp. 893-902. DOI: 10.1049/iet-com.2012.0739.
[16] Robert G. Gallager, “Principles of Digital Communication”, Cambridge University Press, Chapter 1, Section 1.1.
[17] Xiaojun Lin, Ness B. Shroff, R. Srikant, “A Tutorial on Cross-Layer optimization in Wireless Networks ”, IEEE Journal On Selected Areas in Communication, Vol. 24, No. 8, pp. 1452-1463, Aug 2006. DOI: 11.1109/JSAC.2006.879351.
[18] Mung Chiang, Steven H. Low, A. Robert Calderbank, John C. Doyle, “Layering Optimization Decomposition: A Mathematical Theory of Network Architectures”, Proceedings of the IEEE, Vol. 95, No. 1, pp. 255-312, Jan 2007.
[19] R. Olfati-Saber, A. Fax and R.M. Murray, “Consensus and cooperation in networked multi-agent systems”, Proceedings of the IEEE, Vol. 95, No. 1, pp. 215-233, Jan 2007.
[20] A. Kshyap, T. Basar, R. Srikant, “Quantized Consensus”, Automatica, Vol. 43, No.7, pp. 1192-1203, July 2003.
[21] Shreyas Sundaram, Christoforos N. Hadjicostis, “Structural Controllability and Observability of Linear Systems Over Finite Fields with Applications to Multi-Agent Systems”, IEEE Transactions on Automatic Control, Vol. 58, No. 1, pp. 60-73, Jan 2013.
[22] Raymond W. Yung, “Information Theory and Network Coding”, Springer, Aug 2008. ISBN: 978-0-387-79233-0.
[23] Shuo-Yen Robert Li, Raymong W. Yeung, Ning Cai, “Linear Network Coding”, IEEE Transactions on Information Theory, Vol. 49, No. 2, pp. 371-381, Feb 2003.
[24] Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, Raymond W. Yeung, “Network Information Flow”, IEEE Transaction on Information Theory, Vol. 46, No. 4, pp. 1204-1216, July 2003.
[25] R. Koetier and M. Medard, “An algebraic approach to network coding”, IEEE/ACM Transactions on Networking, Vol. 11, No. 5, pp. 782-795. Oct 2003.
[26] R.W. Yeung, S.Y. R. Li, N. Cai and Z.Zhang, “Network Coding Theory”, in Foundations and Trends in Communications and Information theory, Now publishers Inc, Vol. 2, No. 4/5, pp. 241-381.
[27] Abbas El Gamal, Young-Han Kim, “Network Information Theory”, Cambridge University Press, Jan 2012. ISBN: 9781107008731.
[28] L-L. Xie, P.R. Kumar, “Wireless Network Information Theory”, DIMACS Workshop on Network Information Theory, March 2003.
[29] P. Santi, “Topology Control in Wireless Ad Hoc and Sensor Networks”, John Wiley and Sons, Chichester, UK, July 2005.
[30] Soumitra Dutta, INSEAD, Irene Mia, World Economic Forum (Editors), “The Global Information Technology Report 2009-2010”, ICT for sustainability.
[31] M. Grossglauser, David N.C. Tse, “Mobility increases the capacity of ad hoc wireless networks”, IEEE/ACM Transactions on Networking (TON), Vol. 10, No. 4, pp. 477-486, August 2002.
[32] Anand D. Sarwate, Alexandros G. Dimakis, “The impact of Mobility on Gossip Algorithms”, IEEE Transactions on Information Theory, Vol. 58, No. 3, pp. 1731-1742, 2012.
[33] Volkan Rodopolu, Teresa H. Meng, “Bits-per Joule Capacity of Energy-Limited Wireless Networks”, IEEE Transactions on Wireless Communications, Vol. 6, No. 3, pp. 857-865, 2007.
[34] Christian Scheideler, “Overlay Networks for Wireless Systems”. In Chansu Yu (Editor), Performance Analysis of Mobile and Ad Hoc Networks, Wireless Networks and Mobile Computing Series, Vol. 7, Nova Science Publishers, 2007.
[35] Piet Van Mieghem, “Graph Spectra for Complex Networks”, Cambridge University Press, 2011.
[36] Tamaghna Acharya, Rajarshi Roy and Samiran Chattopadhyay, “Energy-Efficient Broadcasting in Wireless Ad Hoc Networks Using Directional Antennas”, IEEE VTC, Singapore, pp. 36-40, 2008.
[37] S. Maulik, A. De, A. Bhattacharya, R. Roy, “”Dynamic Resource Allocation in SINR Constrained Cognitive Radio Network with Imperfect Channel States”, Fourth Nordic Workshop on System and Network Optimization for Wireless, SNOW, April 2-6, 2013, Yllas, Finland.
[38] U. L Wijewardhana, M. Codreanu, M. Latva-aho, “Robust Beam Former Design for underlay Cognitive Radio Network Using Worst Case Optimization”, University of Oulu, Fourth Nordic Workshop on System and Network Optimization for Wireless, SNOW, April 2-6, 2013, Yllas, Finland.
[39] Nawar M. El Molla, “Yao Spanners for Wireless Ad Hoc Networks”, MS thesis, CS Dept., Villanova University, 2009. (Research Supervisor: Mirela Damian)
[40] Fabian Kuhn, Thomas Moscibroda and Roger Wattenhofer, “Unit Disk Graph Approximation”, DIALM-POMC’04, Philadelphia, Pennsylvania, USA, 2004.
[41] Prosenjit Bose, Joachim Gudmundsson and Pat Morin “Ordered theta graphs”, Computational Geometry, No. 28, pp. 11-18, 2004. DOI:10.1016/j.comgeo.2004.01.003.
[42] Xiang-Yang Li, Wen-Zhan Song and Yu Wang, “Efficient Topology Control for Ad-Hoc Wireless Networks with Non-Uniform Transmission Ranges”, Wireless Networks, Springer, Netherlands, Vol. 11, pp. 255-264, 2005.
[43] Khaled Alzoubi, Xiang-Yang Li,Yu Wang, Peng-Jun Wan, and Ophir Frieder, “Geometric Spanners for Wireless Ad Hoc Networks”, IEEE Transactions on parallel and Distributed Systems, Vol. 14, No. 5, pp. 1-14, 2003.
[44] Intae Kang, Radha Pooverdran,, “Maximizing network lifetime of broadcasting over wireless stationary ad hoc networks”, Vol. 10, No. 6, pp. 879-896, Dec 2005.
[45] J.E. Wieselthier, G.D. Nguyen and A. Ephremides, “On the construction of energy-efficient broadcast and multicast trees in wireless networks”, IEEE INFOCOM 2000, Vol. 2, pp. 585-594, Tel Aviv, Israel.
[46] Zhifeng Tao, Thanasis Korakis, Feilu Liu, Shivendra Panwar, Jinyun Zhang, Leandros Tassiulas, “Cooperation and Directionality: Friends or Foes?”, IEEE ICC, Beijing, China, pp. 4424-4430, 2008.
[47] J. Czyzowicz, S. Dobrev, E. Kranakis, J. Opatrny, J. Urrutia “Local Edge Colouring of Yao-like Sub graphs of Unit Disk Graphs”, LNCS 4474, pp. 195-207, Heidelberg, Berlin, 2007.
[48] Iyad A. Kanj and Ge Xia, “On certain geometric properties of the Yao–Yao graphs”, Springer, New York, USA, Nov. 2012. DOI: 10.1007/s10878-012-9570-z.
[49] Prosenjit Bose, Andre van Renssen and Sander Verdonschot, “On the Spanning Ratio of Theta-Graphs”, Springer-Verlag, WADS, LNCS 8037, pp. 182-194, Heidelberg, Berlin, 2013.
[50] P. Gupta, P.R. Kumar, “The Capacity of Wireless Networks”, IEEE Transactions on Information Theory, Vol. 46, No. 2, pp. 388-402.
[51] Vahid Tarokh, Nambi Seshadri and A.R. Calderbank, “Space-time codes for high data wireless communication: Performance analysis and code construction”, IEEE Transactions on Information Theory,, Vol. 44, No. 2, pp. 744-765. DOI: 10.1109/18.661517.
[52] Sushant Sharma, Yi Shi, Jia Liu, Y. Thomas Hou, Sastry Kompella, Scott F. Midkiff, “Network Coding in Cooperative Communications: Friend or Foe?”, IEEE Transactions on Mobile Computing, Vol. 11, No. 7, pp. 1073-1085, July 2012.