Exact and heuristic methods for sensor allocation on large and irregular wireless networks

Exact and heuristic methods for sensor allocation on large and irregular wireless networks | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Exact and heuristic methods for sensor allocation on large and irregular wireless networks Diego Rodrigues Moreira Totte, Felipe da Rocha Henriques, Pedro Henrique Gonzalez Silva, and 4 more This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-4619085/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Wireless Sensor Networks (WSNs) have become ubiquitous across various domains, from household applications to industrial grounds, and critical areas like emergency response and environmental monitoring. While numerous optimization techniques have emerged in the literature to enhance network performance by strategically allocating sensor nodes, most studies in this field rely on heuristic methods. Designing the topology of WSNs is crucial for optimizing node energy consumption, connectivity, and coverage area. In this work, two methodologies are proposed to minimize the overall energy consumption of the network. The first is an exact method using a Mixed Integer Linear Programming (MILP) model. The second is an optimization method based on genetic algorithms (GAs). In the computational experiments, instances were generated based on grid-like networks, some of which assuming highly irregular topologies. The results have shown that the exact approach found optimal solutions for some instances, up to five thousand nodes. In contrast, the GA obtained high-quality solutions for instances with more than 18 thousand nodes in reasonable computational times. Wireless Sensor Network Combinatorial Optimization Mixed Integer Linear Programming Genetic Algorithms Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-4619085","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":317695453,"identity":"5d75d37f-f8b4-4341-8130-84a929c326ec","order_by":0,"name":"Diego Rodrigues Moreira Totte","email":"","orcid":"","institution":"Federal Center for Technological Education Celso Suckow da Fonseca","correspondingAuthor":false,"prefix":"","firstName":"Diego","middleName":"Rodrigues Moreira","lastName":"Totte","suffix":""},{"id":317695454,"identity":"572bc2d3-e8c5-4d65-b2a2-79d2145cc3f6","order_by":1,"name":"Felipe da Rocha Henriques","email":"","orcid":"","institution":"Federal Center for Technological Education Celso Suckow da Fonseca","correspondingAuthor":false,"prefix":"","firstName":"Felipe","middleName":"da Rocha","lastName":"Henriques","suffix":""},{"id":317695455,"identity":"0031b316-7893-429e-92c6-0c78f54b49db","order_by":2,"name":"Pedro Henrique Gonzalez Silva","email":"","orcid":"","institution":"Federal University of Rio de Janeiro","correspondingAuthor":false,"prefix":"","firstName":"Pedro","middleName":"Henrique Gonzalez","lastName":"Silva","suffix":""},{"id":317695456,"identity":"7cb8d5ad-8c84-4467-bd94-d7cf43e25cd4","order_by":3,"name":"Fábio Luiz Usberti","email":"","orcid":"","institution":"State University of Campinas","correspondingAuthor":false,"prefix":"","firstName":"Fábio","middleName":"Luiz","lastName":"Usberti","suffix":""},{"id":317695457,"identity":"d7b3c75f-d38e-4ca0-a47d-7c983f12231f","order_by":4,"name":"Douglas O. Cardoso","email":"","orcid":"","institution":"University of Porto","correspondingAuthor":false,"prefix":"","firstName":"Douglas","middleName":"O.","lastName":"Cardoso","suffix":""},{"id":317695458,"identity":"2aabf700-44e9-4f87-a67f-b541a30ebabb","order_by":5,"name":"Eduardo Ogasawara","email":"","orcid":"","institution":"Federal Center for Technological Education Celso Suckow da Fonseca","correspondingAuthor":false,"prefix":"","firstName":"Eduardo","middleName":"","lastName":"Ogasawara","suffix":""},{"id":317695459,"identity":"a401db91-c0fa-48dc-a60d-3f38af72b14b","order_by":6,"name":"Laura Silva de Assis","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA+0lEQVRIiWNgGAWjYBACPjiLmYHxAQODHJhtwNiAWwsbkhZmAwYGYwYe4rUA2RIwLQx4tbCfMfvwg8HOXr6d/VnFjwoDOXsG3gcFjDvu4dbCk2M8s4chOXHDYR6zmz1nDIx5GNgNDBjPFONxWA7ILcwJBsw8bLcZ2/4k9sg/A/qlLQG3Fv43xox/GOrt5ZvZnxUz/jOo7wEag1+LRI4xMw/DYcaGwwxmzIwNBgk8hLU8K2aWMTgO8ouxZM8xA8OeA0AtiWdwa+HnT97M+Kai2l6+//jDDz9qDOTZG9jYDD7uwK0FAgzQrDYgpAEDMD8gVccoGAWjYBQMawAATthBclhySQQAAAAASUVORK5CYII=","orcid":"","institution":"Federal Center for Technological Education Celso Suckow da Fonseca","correspondingAuthor":true,"prefix":"","firstName":"Laura","middleName":"Silva","lastName":"de Assis","suffix":""}],"badges":[],"createdAt":"2024-06-21 19:29:48","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-4619085/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-4619085/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":73146352,"identity":"f530d518-f6bf-4c4a-96de-43db37d03d47","added_by":"auto","created_at":"2025-01-07 07:47:14","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":1470400,"visible":true,"origin":"","legend":"","description":"","filename":"GAXMILPSensorAllocationOptimizationWSN.pdf","url":"https://assets-eu.researchsquare.com/files/rs-4619085/v1_covered_794fe53b-1908-4b17-b2a2-be574670b5f2.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Exact and heuristic methods for sensor allocation on large and irregular wireless networks","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Wireless Sensor Network, Combinatorial Optimization, Mixed Integer Linear Programming, Genetic Algorithms","lastPublishedDoi":"10.21203/rs.3.rs-4619085/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-4619085/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Wireless Sensor Networks (WSNs) have become ubiquitous across various domains, from household applications to industrial grounds, and critical areas like emergency response and environmental monitoring. While numerous optimization techniques have emerged in the literature to enhance network performance by strategically allocating sensor nodes, most studies in this field rely on heuristic methods. Designing the topology of WSNs is crucial for optimizing node energy consumption, connectivity, and coverage area. In this work, two methodologies are proposed to minimize the overall energy consumption of the network. The first is an exact method using a Mixed Integer Linear Programming (MILP) model. The second is an optimization method based on genetic algorithms (GAs). In the computational experiments, instances were generated based on grid-like networks, some of which assuming highly irregular topologies. The results have shown that the exact approach found optimal solutions for some instances, up to five thousand nodes. In contrast, the GA obtained high-quality solutions for instances with more than 18 thousand nodes in reasonable computational times.","manuscriptTitle":"Exact and heuristic methods for sensor allocation on large and irregular wireless networks","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-07-12 10:43:13","doi":"10.21203/rs.3.rs-4619085/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"91985928-af70-4d1c-921d-ef0ac25a40e9","owner":[],"postedDate":"July 12th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2025-01-07T07:39:05+00:00","versionOfRecord":[],"versionCreatedAt":"2024-07-12 10:43:13","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-4619085","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-4619085","identity":"rs-4619085","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}