{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,1]],"date-time":"2024-04-01T18:40:44Z","timestamp":1711996844007},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T00:00:00Z","timestamp":1291334400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2010,12,3]],"date-time":"2010-12-03T00:00:00Z","timestamp":1291334400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Braz Comput Soc"],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Clustering is a fundamental mechanism used in the design of Wireless Sensor Network (WSN) protocols. The performance of WSNs can be improved by selecting the most suitable nodes to form a stable backbone structure with guaranteed network coverage. This paper proposes a base station-controlled centralized algorithm for static sensor networks and a distributed, weighted algorithm for dynamic sensor networks. The solutions are based on a (<jats:italic>k<\/jats:italic>,<jats:italic>r<\/jats:italic>)-<jats:italic>Connected Dominating Set<\/jats:italic>, which is suitable for cluster-based hierarchical routing. The clusterhead redundancy parameter<jats:italic>k<\/jats:italic>improves reliability, the multi-hop parameter<jats:italic>r<\/jats:italic>addresses the scalability issue and the combined weight metric improves the network lifespan and reduces the number of re-affiliations. To create a stable and efficient backbone structure, the backbone sensor nodes are selected based on quality, which is a function of the residual battery power, node degree, transmission range, and mobility of the sensor nodes. Simulation experiments are conducted to evaluate the performance of both the algorithms in terms of the number of elements in the backbone structure, re-affiliation frequency, load balancing, network lifespan, and the power dissipation. The results establish the potential of these algorithms for use in WSNs.<\/jats:p>","DOI":"10.1007\/s13173-010-0024-0","type":"journal-article","created":{"date-parts":[[2010,12,2]],"date-time":"2010-12-02T16:00:54Z","timestamp":1291305654000},"page":"3-18","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Application oriented connected dominating set-based cluster formation in wireless sensor networks"],"prefix":"10.1007","volume":"17","author":[{"given":"V. S.","family":"Anitha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. P.","family":"Sebastian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,12,3]]},"reference":[{"issue":"5","key":"24_CR1","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1109\/2.841788","volume":"33","author":"J Agre","year":"2000","unstructured":"Agre J, Clare L (2000) An integrated architecture for cooperative sensing networks. Computer 33(5):106\u2013108","journal-title":"Computer"},{"issue":"3","key":"24_CR2","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.adhoc.2003.09.010","volume":"3","author":"K Akkaya","year":"2005","unstructured":"Akkaya K, Younis M (2005) A survey on routing protocols for wireless sensor networks. Ad Hoc Netw 3(3):325\u2013349","journal-title":"Ad Hoc Netw"},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"Akyildiz IF, Su W, Sankaraubramaniam Y, Cayirci E (2002) A\u00a0survey on sensor networks. IEEE Commun Mag","DOI":"10.1109\/MCOM.2002.1024422"},{"issue":"8","key":"24_CR4","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1109\/MCOM.2002.1024422","volume":"40","author":"IF Akylidiz","year":"2002","unstructured":"Akylidiz IF, Su W, Sankarasubramanian Y, Cayirci E (2002) Wireless sensor network: A survey on sensor network. IEEE Commun Mag 40(8):102\u2013114","journal-title":"IEEE Commun Mag"},{"issue":"1","key":"24_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4018\/jmcmc.2009010101","volume":"1","author":"VS Anitha","year":"2009","unstructured":"Anitha VS, Sebastian MP (2009) Scenario-based cluster formationand management in mobile ad hoc networks. Int J Mobile Comput Multimedia Commun 1(1):1\u201315 (IGI Journal)","journal-title":"Int J Mobile Comput Multimedia Commun"},{"key":"24_CR6","first-page":"97","volume-title":"13th IEEE\/ACM international symposium on distributed simulation and real time applications","author":"VS Anitha","year":"2009","unstructured":"Anitha VS, Sebastian MP (2009) Scenario-based diameter-bounded algorithm for cluster creation and management in mobile ad hoc networks. In: 13th IEEE\/ACM international symposium on distributed simulation and real time applications, pp 97\u2013104"},{"key":"24_CR7","volume-title":"Handbook of combinatorial optimization","author":"J Blum","year":"2004","unstructured":"Blum J, Ding M, Thaeler A, Cheng X (2004) Connected dominating set in sensor networks and MANETs. In: Du D-Z, Pardalos\u00a0P (eds) Handbook of combinatorial optimization. Kluwer Academic, Amsterdam"},{"issue":"5","key":"24_CR8","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1109\/98.878531","volume":"7","author":"P Bonnet","year":"2000","unstructured":"Bonnet P, Gehrke J, Seshadri P (2000) Querying the physical world. IEEE Pers Commun 7(5):10\u201315","journal-title":"IEEE Pers Commun"},{"key":"24_CR9","volume-title":"International symposium on communication theory and applications (ISCTA 2001)","author":"N Bulusu","year":"2001","unstructured":"Bulusu N, Estrin D, Girod L, Heidemann J (2001) Scalable coordination for wireless sensor networks: self-configuring localization systems. In: International symposium on communication theory and applications (ISCTA 2001). Ambleside, UK, 2001"},{"issue":"9","key":"24_CR10","doi-asserted-by":"publisher","first-page":"6869","DOI":"10.3390\/s90906869","volume":"9","author":"C Buratti","year":"2009","unstructured":"Buratti C, Conti A, Dardari D, Verdone R (2009) An overview on wireless sensor networks technology and evolution. Sensors 9(9):6869\u20136896","journal-title":"Sensors"},{"issue":"1","key":"24_CR11","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1023\/A:1013941929408","volume":"5","author":"M Chatterjee","year":"2002","unstructured":"Chatterjee M, Das SK, Turgut D (2002) Wca: a weighted clustering algorithm for mobile ad hoc networks. Clust Comput 5(1):193\u2013204","journal-title":"Clust Comput"},{"key":"24_CR12","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1145\/513800.513821","volume-title":"MobiHoc","author":"Y Chen","year":"2002","unstructured":"Chen Y, Lieshman AL (2002) Approximating minimum size weakly connected dominating sets for clustering mobile ad hoc networks. In: MobiHoc. ACM Press, New York, pp 165\u2013172"},{"key":"24_CR13","first-page":"371","volume-title":"ICE","author":"B Das","year":"1997","unstructured":"Das B, Bhargavan V (1997) Routing in ad hoc networks using minimum connected dominating set. In: ICE, pp 371\u2013380"},{"key":"24_CR14","first-page":"22","volume-title":"Proceedings for the 6th international conference on computer communications and networks (IC3N\u201997)","author":"B Das","year":"1997","unstructured":"Das B, Sivakumar E, Bhargavan V (1997) Routing in ad hoc networks using a virtual backbone. In: Proceedings for the 6th international conference on computer communications and networks (IC3N\u201997), Las Vegas, NV, USA, 1997, pp 22\u201325"},{"key":"24_CR15","volume-title":"Proc of international conference on computers and communications networks, ICCCN","author":"B Das","year":"1997","unstructured":"Das B, Sivakumar R, Bharghavan V (1997) Routing in ad-hoc networks using a spine. In: Proc of international conference on computers and communications networks, ICCCN, Las Vegas, 1997"},{"key":"24_CR16","volume-title":"Proc of the IEEE international conference on distributed computing in sensor systems","author":"P Ding","year":"2005","unstructured":"Ding P, Holliday J, Celek A (2005) Distributed energy efficient hierarchical clustering for wireless sensor networks. In: Proc of the IEEE international conference on distributed computing in sensor systems"},{"key":"24_CR17","first-page":"254","volume-title":"Proceedings of IRE","author":"Friis","year":"1946","unstructured":"Friis: (1946) A note on simple transmission formula. In: Proceedings of IRE, pp 254\u2013256"},{"key":"24_CR18","unstructured":"Garey M, Johnson D (1978) Computers and intractability: a guide to NP-completeness"},{"key":"24_CR19","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/PL00009201","volume":"20","author":"S Guha","year":"1998","unstructured":"Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20:374\u2013387","journal-title":"Algorithmica"},{"issue":"1","key":"24_CR20","first-page":"9","volume":"14","author":"B Halweil","year":"2001","unstructured":"Halweil B (2001) Study finds modern farming is costly. World Watch 14(1):9\u201310","journal-title":"World Watch"},{"issue":"4","key":"24_CR21","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1109\/TWC.2002.804190","volume":"1","author":"W Heinzelman","year":"2002","unstructured":"Heinzelman W, Chandrakasan A, Balakrishnan H (2002) An application-specific protocol architecture for wireless microsensor networks. IEEE Trans Wirel Commun 1(4):660\u2013670","journal-title":"IEEE Trans Wirel Commun"},{"issue":"2","key":"24_CR22","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1258\/1357633961929871","volume":"2","author":"P Johnson","year":"1996","unstructured":"Johnson P, Andrews DC (1996) Remote continuous physiological monitoring in the home. J Telemed Telecare 2(2):107\u2013113","journal-title":"J Telemed Telecare"},{"key":"24_CR23","first-page":"271","volume-title":"Proceedings of the ACM MobiCom\u201999","author":"J Kahn","year":"1999","unstructured":"Kahn J, Katz R, Pister K (1999) Next century challenges: mobile networking for smart dust. In: Proceedings of the ACM MobiCom\u201999. Washington, USA, 1999, pp 271\u2013278"},{"key":"24_CR24","doi-asserted-by":"crossref","unstructured":"Li J, Andrew LL, Foh CH, Zukerman M, Chen HH (2009) Connectivity, coverage and placement in wireless sensor networks. Sensors","DOI":"10.3390\/s91007664"},{"key":"24_CR25","volume-title":"Proc of IEEE aerospace conference","author":"S Lindsey","year":"2002","unstructured":"Lindsey S, Raghavendra CS (2002) Pegasis: power efficient gathering in sensor information systems. In: Proc of IEEE aerospace conference. IEEE"},{"key":"24_CR26","first-page":"607","volume-title":"IEEE-EMBS special topic conference on microtechnologies in medicine and biology","author":"N Noury","year":"2000","unstructured":"Noury N, Herve T, Rialle V, Virone G, Mercier E, Morey G, Moro A, Porcheron T (2000) Monitoring behavior in home using a smart fall sensor. In: IEEE-EMBS special topic conference on microtechnologies in medicine and biology, pp 607\u2013610"},{"key":"24_CR27","first-page":"397","volume-title":"Proceedings ICPADS","author":"V Paruchuri","year":"2005","unstructured":"Paruchuri V, Durresi A, Durresi M, Barolli L (2005) Routing through back bone structures in sensor networks. In: Proceedings ICPADS, ICPADS, Japan, 2005, pp 397\u2013401"},{"key":"24_CR28","doi-asserted-by":"crossref","unstructured":"Rabaey J, Ammer M, da Silva J Jr, Patel D, Roundy S (2000) Picoradio supports ad hoc ultra-low power wireless networking. IEEE Comput Mag","DOI":"10.1109\/2.869369"},{"key":"24_CR29","series-title":"Handbook of sensor networks","volume-title":"Energy-efficient backbone construction, broadcasting, and area coverage in sensor networks","author":"DS Ryl","year":"2005","unstructured":"Ryl DS, Stojmenovic I, Wu J (2005) Energy-efficient backbone construction, broadcasting, and area coverage in sensor networks. Handbook of sensor networks. Wiley, New York"},{"key":"24_CR30","volume-title":"20th annual joint conference of the IEEE computer and communications societies","author":"P Sinha","year":"2001","unstructured":"Sinha P, Sivakumar R, Bharghavan V (2001) Enhancing ad hoc routing with dynamic virtual infrastructures. In: 20th annual joint conference of the IEEE computer and communications societies, vol\u00a03"},{"key":"24_CR31","volume-title":"Mobile ad hoc networking","author":"I Stojmenovic","year":"2004","unstructured":"Stojmenovic I, Wu J (2004) Broadcasting and activity scheduling in AD HOC networks. In: Basagni S, Conti M, Giordano S, Stojmenovic I (eds) Mobile ad hoc networking. IEEE, New York"},{"key":"24_CR32","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1023\/B:MONE.0000013625.87793.13","volume":"9","author":"PJ Wan","year":"2004","unstructured":"Wan PJ, Alzoubi KM, Frieder O (2004) Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Netw Appl 9:141\u2013149","journal-title":"Mobile Netw Appl"},{"key":"24_CR33","volume-title":"Smart dust: communicating with a cubic-millimeter computer","author":"B Warneke","year":"2001","unstructured":"Warneke B, Liebowitz B, Pister K (2001) Smart dust: communicating with a cubic-millimeter computer. IEEE Computer, New York"},{"key":"24_CR34","unstructured":"Wu J, Li H On calculating connected dominating set for efficient routing in ad hoc wireless networks. In: Proc of proceedings of the 3rd ACM international workshop on discrete algorithms and methods for mobile computing and communications, pp. 7\u201314. ACM, New York"},{"key":"24_CR35","volume-title":"Mobihoc 2008","author":"Y Wu","year":"2008","unstructured":"Wu Y, Li Y (2008) Construction algorithms for k-connected m-dominating sets in wireless sensor networks. In: Mobihoc 2008"},{"key":"24_CR36","first-page":"29","volume-title":"Military communications conference","author":"Y Wu","year":"2007","unstructured":"Wu Y, Wang F, Thai MT, Li Y (2007) Constructing k-connected m-dominating sets in wireless sensor networks. In: Military communications conference. MILCOM, Orlando, pp 29\u201331"},{"issue":"4","key":"24_CR37","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1109\/TMC.2004.41","volume":"3","author":"O Younis","year":"2004","unstructured":"Younis O, Fahmy S (2004) Heed: A hybrid energy-efficient distributed clustering approach for ad hoc sensor networks. IEEE Trans Mob Comput 3(4):366\u2013379","journal-title":"IEEE Trans Mob Comput"}],"container-title":["Journal of the Brazilian Computer Society"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-010-0024-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13173-010-0024-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-010-0024-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-010-0024-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,1]],"date-time":"2024-04-01T18:26:23Z","timestamp":1711995983000},"score":1,"resource":{"primary":{"URL":"https:\/\/journal-bcs.springeropen.com\/articles\/10.1007\/s13173-010-0024-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12,3]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["24"],"URL":"https:\/\/doi.org\/10.1007\/s13173-010-0024-0","relation":{},"ISSN":["0104-6500","1678-4804"],"issn-type":[{"value":"0104-6500","type":"print"},{"value":"1678-4804","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12,3]]},"assertion":[{"value":"3 February 2010","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2010","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2010","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}