Borel Cayley graphs have been shown to be an efficient candidate topology in interconnection networks due to their small diameter, short path length, and low degree. In this paper, we propose topology control algorithms based on Borel Cayley graphs. In particular, we propose two methods to assign node IDs of Borel Cayley graphs as logical topologies in wireless sensor networks. The first one aims at minimizing communication distance between nodes, while the entire graph is imposed as a logical topology; while the second one aims at maximizing the number of edges of the graph to be used, while the network nodes are constrained with a finite radio transmission range. In the latter case, due to the finite transmission range, the resultant topology is an “incomplete” version of the original BCG. In both cases, we apply our algorithms in consensus protocol and compare its performance with that of the random node ID assignment and other existing topology control algorithms. Our simulation indicates that the proposed ID assignments have better performance when consensus protocols are used as a benchmark application. 1. Introduction An adhoc wireless sensor network (WSN) is a self-organized and distributed network consisting of a large number of small and light sensor nodes [1, 2]. A sensor node includes a processor, a wireless radio, and various sensors to monitor and sense environmental parameters such as temperature, moisture, and pressure. In a WSN, sensor nodes interchange information and collaborate with each other to achieve a common mission. The flexibility, fault tolerance, high sensing fidelity, low cost, and rapid deployment characteristics of sensor networks create many new and exciting application areas for remote sensing [3]. Examples of ad-hoc wireless sensor networks applications include building monitoring [4], environmental sensing [5–7], traffic monitoring [8], and surveillance [9]. Some WSN applications require very dense networks. Hundreds to several thousands of nodes can be deployed throughout a sensor field. For example, some machine diagnosis applications use up to 3000 nodes in a 100？m by 100？m area [10] or sensors can be deployed within tens of feet of each other for object tracking [11]. The topology of a large and dense sensor network is important to its performance. For example, topology control algorithms are essential in reducing energy consumption and radio interference [12], thus expanding the network’s lifetime. According to [13], topology control algorithms can be classified as location-based, direction-based, or
References
[1]
D. Culler, D. Estrin, and M. Srivastava, “Introduction: overview of sensor networks,” Computer, vol. 37, no. 8, pp. 41–49, 2004.
[2]
I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, vol. 40, no. 8, pp. 102–114, 2002.
[3]
C. E. Perkins, “Ad hoc networking: an introduction,” in Ad Hoc Networking, pp. 1–28, Addison-Wesley Longman, Boston, Mass, USA, 2001.
[4]
T. Schmid, H. Dubois-ferriere, and M. Vetterli, “Sensorscope: experiences with a wireless building monitoring sensor network,” in Proceedings of the 1st Workshop on Real-World Wireless Sensor Networks (REALWSN '05), 2005.
[5]
G. Werner-Allen, K. Lorincz, M. Welsh et al., “Deploying a wireless sensor network on an active volcano,” IEEE Internet Computing, vol. 10, no. 2, pp. 18–25, 2006.
[6]
L. Selavo, A. Wood, Q. Cao et al., “LUSTER: wireless sensor network for environmental research,” in Proceedings of the 5th ACM International Conference on Embedded Networked Sensor Systems (SenSys '07), pp. 103–116, November 2007.
[7]
K. Martinez, J. K. Hart, and R. Ong, “Environmental sensor networks,” Computer, vol. 37, no. 8, pp. 50–56, 2004.
[8]
S. Coleri, S. Y. Cheung, and P. Varaiya, “Sensor networks for monitoring traffic,” in Proceedings of the Allerton Conference on Communication, Control and Computing, 2004.
[9]
T. Yan, T. He, and J. A. Stankovic, “Differentiated surveillance for sensor networks,” in Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys '03), pp. 51–62, November 2003.
[10]
E. Shih, S.-H. Cho, N. Ickes et al., “Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks,” in Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, pp. 272–287, New York, NY, USA, July 2001.
[11]
C. Intanagonwiwat, R. Govindan, and D. Estrin, “Directed diffusion: a scalable and robust communication paradigm for sensor networks,” in Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM '00), pp. 56–67, August 2000.
[12]
R. Rajaraman, “Topology control and routing in ad hoc networks: a survey,” SIGACT News, vol. 33, pp. 60–73, 2002.
[13]
P. Santi, “Topology control in wireless ad hoc and sensor networks,” ACM Computing Surveys, vol. 37, no. 2, pp. 164–194, 2005.
[14]
S. B. Akers and B. Krishnamurthy, “A group-theoretic model for symmetric interconnection networks,” IEEE Transactions on Computers, vol. 38, no. 4, pp. 555–566, 1989.
[15]
K. N. Sivarajan and R. Ramaswami, “Lightwave networks based on de Bruijn graphs,” IEEE/ACM Transactions on Networking, vol. 2, no. 1, pp. 70–79, 1994.
[16]
J. Sun and E. Modiano, “Capacity provisioning and failure recovery for Low Earth Orbit satellite constellation,” International Journal of Satellite Communications and Networking, vol. 21, no. 3, pp. 259–284, 2003.
[17]
T. Bjerregaard and S. Mahadevan, “A survey of research and practices of network-on-chip,” ACM Computing Surveys, vol. 38, no. 1, pp. 71–121, 2006.
[18]
E. K. Lua, J. Crowcroft, M. Pias, R. Sharma, and S. Lim, “A survey and comparison of peer-to-peer overlay network schemes,” IEEE Communications Surveys & Tutorials, vol. 7, no. 2, pp. 72–93, 2005.
[19]
I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, “Chord: a scalable peer-to-peer lookup service for internet applications,” in Proceedings of the Applications, Technologies, Architectures, and Protocols for Computers Communications (ACM SIGCOMM '01), pp. 149–160, New York, NY, USA, August 2001.
[20]
M. F. Kaashoek and D. R. Karger, “Koorde: a simple degree-optimal distributed hash table,” in Peer-to-Peer Systems II, vol. 2735 of Lecture Notes in Computer Science, pp. 98–107, 2003.
[21]
M. Naor and U. Wieder, “Novel architectures for P2P applications: the continuous-discrete approach,” ACM Transactions on Algorithms, vol. 3, no. 3, Article ID 1273350, 2007.
[22]
D. Loguinov, J. Casas, and X. Wang, “Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience,” IEEE/ACM Transactions on Networking, vol. 13, no. 5, pp. 1107–1120, 2005.
[23]
C. Qu, W. Nejdl, and M. Kriesell, “Cayley dhts—a group-theoretic framework for analyzing dhts based on cayley graphs,” in Proceedings of the International Symposium on Parallel and Distributed Processing and Applications (ISPA '04), Springer, 2004.
[24]
S. S. Iyengar, D. N. Jayasimha, and D. Nadig, “A versatile architecture for the distributed sensor integration problem,” IEEE Transactions on Computers, vol. 43, no. 2, pp. 175–185, 1994.
[25]
A. A. Taleb, J. Mathew, and D. K. Pradhan, “Fault diagnosis in multi layered De Bruijn based architectures for sensor networks,” in Proceedings of the 8th IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOM Workshops '10), pp. 456–461, April 2010.
[26]
A. A.-B. Al-Mamou and H. Labiod, “ScatterPastry: an overlay routing using a DHT over wireless sensor networks,” in Proceedings of the International Conference on Intelligent Pervasive Computing (IPC '07), pp. 274–279, kor, October 2007.
[27]
M. Caesar, M. Castro, E. B. Nightingale, G. O’Shea, and A. Rowstron, “Virtual ring routing: network routing inspired by dhts,” in Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM ’06), pp. 351–362, ACM, New York, NY, USA, 2006.
[28]
F. Araujo, L. Rodrigues, J. Kaiser, C. Liu, and C. Mitidieri, “Chr: a distributed hash table for wireless ad hoc networks,” in Proceedings of the 25th IEEE International Conference on Distributed Computing Systems Workshops, pp. 407–413, 2005.
[29]
K. W. Tang and B. W. Arden, “Representations of borel cayley graphs,” SIAM Journal on Discrete Mathematics, vol. 6, pp. 655–676, 1993.
[30]
B. W. Arden and K. W. Tang, “Representations and routing for Cayley graphs,” IEEE Transactions on Communications, vol. 39, no. 11, pp. 1533–1537, 1991.
[31]
K. W. Tang and B. W. Arden, “Vertex-transitivity and routing for Cayley graphs in GCR representations,” in Proceedings of the ACM/SIGAPP Symposium on Applied Computing (SAC '92), pp. 1180–1187, March 1992.
[32]
R. Olfati-Saber, J. 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, 2007.
[33]
J. Yu, E. Noel, and K. W. Tang, “A graph theoretic approach to ultrafast information distribution: borel Cayley graph resizing algorithm,” Computer Communications, vol. 33, no. 17, pp. 2093–2104, 2010.
[34]
J. Ryu, J. Yu, E. Noel, and K. Tang, “Node id assignment in group theoretic graphs for wsns,” in Proceedings of the Wireless Telecommunications Symposium (WTS '11), pp. 1–8, 2011.
[35]
L. Xiao, S. Boyd, and S. Lall, “A scheme for robust distributed sensor fusion based on average consensus,” in Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN '05), pp. 63–70, April 2005.
[36]
Y. Hatano and M. Mesbahi, “Agreement over random networks,” in Proceedings of the 43rd IEEE Conference on Decision and Control (CDC '04), vol. 2, pp. 2010–2015, December 2004.
[37]
L. Schenato and G. Gamba, “A distributed consensus protocol for clock synchronization in wireless sensor network,” in Proceedings of the 46th IEEE Conference on Decision and Control (CDC '07), pp. 2289–2294, December 2007.
[38]
P. Braca, S. Marano, and V. Matta, “Running consensus in wireless sensor networks,” in Proceedings of the 11th International Conference on Information Fusion (FUSION '08), pp. 1–6, July 2008.
[39]
A. G. Dimakis, S. Kar, J. M. F. Moura, M. G. Rabbat, and A. Scaglione, “Gossip algorithms for distributed signal processing,” Proceedings of the IEEE, vol. 98, no. 11, pp. 1847–1864, 2010.
[40]
R. Olfati-Saber and R. M. Murray, “Consensus problems in networks of agents with switching topology and time-delays,” IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1520–1533, 2004.
[41]
R. Olfati-Saber, “Ultrafast consensus in small-world networks,” in Proceedings of the American Control Conference (ACC '05), vol. 4, pp. 2371–2378, June 2005.
[42]
M. Marta and M. Cardei, “Using sink mobility to increase wireless sensor networks lifetime,” in Proceedings of the 9th IEEE International Symposium on Wireless, Mobile and Multimedia Networks (WoWMoM '08), pp. 1–10, June 2008.
[43]
N. Li, J. C. Hou, and L. Sha, “Design and analysis of an MST-based topology control algorithm,” IEEE Transactions on Wireless Communications, vol. 4, no. 3, pp. 1195–1206, 2005.
[44]
D. M. Blough, M. Leoncini, G. Resta, and P. Santi, “The K-Neigh protocol for symmetric topology control in ad hoc networks,” in Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing (MOBIHOC '03), pp. 141–152, New York, NY, USA, June 2003.
[45]
B. Karp and H. T. Kung, “GPSR: Greedy Perimeter Stateless Routing for wireless networks,” in Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM '00), pp. 243–254, August 2000.
