Research Of The Relay Node Placement Based On Greedyalgorithm In Wireless Sensor Networks

Nodes in wireless sensor network are generally powered by the batteries, and theenergy is limited. It is hard to replenish energy in the wireless sensor networkdeployment environment, which is complex and inaccessible. Studies have shownrelaying data in the way of short distance and multi-hop can reduce energy consumption,so in the early network placement, how can relay nodes, which have the function ofrounting, be placed in the network and multi-hop rounting mechanism is used totransmit data? That is related to the research of the relay node placement.Research of relay node placement algorithm at home and abroad is at thepreliminary stage currently. When setting relay nodes, any restrictions are hardlyconsidered. However, wireless sensor network is highly correlated with the application,and locations of relay nodes are limited by many physical factors in the practicalapplication. In order to solve this problem, this article studies the relay node placementalgorithm with constraints, and the main research contents are as follows:1. In the article, we do research on application-oriented relay node placementproblem. A preliminary two-tiered relay node placement model is set up according tothe related knowledge of graph theory, and the relay node placement problem istranslated into a route choice problem in graph theory. Constraints, such as themaximum hop count of sensor node data forwarding, the communication path selectioncriteria and communication capacity, are added to optimize the model. Based on greedyalgorithm thoughts, we establish the nearest mechanism greedy criterion.When the localoptimization problem comes up, the empty hole circumventing method can be used tosolve it. In a word, we mainly adopt greedy algorithm to carry on the design schemes ofrelay node placement algorithm and empty hole circumventing method iscomplementary.2. When wireless sensor network distribution is ribbon, we evolve the ribbonnetwork into a linear network, and design a relay node greedy placement algorithmbased on the linear structure. The locations of relay nodes are limited by the nearestmechanism greedy criterion, the minimum greedy criterion and constraints. Theoreticalanalysis and simulation experiment show that the algorithm can reduce network energyconsumption and prolong the network lifetime.3. As for relay node placement problem in a complex environment, we propose arelay node greedy placement algorithm based on the grid structure. The algorithmdetermines the grid spacing on the basis of the change trend of RSSI value or LQI valuewith communication distance. The candidate locations for relay nodes are at the gridintersection. The optimal locations of relay nodes are chosen from the candidate locations according to the nearest mechanism greedy criterion and the minimum anglereserved method. Without local optimization problem, we prove that lower limit of dataforwarding between the sensor nodes and sink node exsits. Theoretical analysis andexperimental results show that the relay node placement algorithm based on the gridstructure can reduce the number of relay nodes and energy consumption.