in this lecture will try to understand a very important concept which is the ah coverage the concept of coverage in sensor networks coverage is a very important problem because what is required is using sensors or sensor networks we have to deploy the sensors or more specifically the sensor nodes in a particular terrain in such a way that no point or no none of the areas in that particular terrain left unsensed in that region so we have to deploy the sensors in such a way that none of the points in the terrain of interest which has to be that means which has to be sensed which has to be [surve/surveilled] surveilled it should not happen that there is such a point which is not within the sensing range of if any sensor node so this is basically known as the point coverage like this there are different other types of coverage called area coverage ah then we have barrier coverage and different other types of coverage ah which have ah been researched upon ah in the literature so we will try to understand this concept first so we have an area of interest and what is required is to ensure that that particular area of interest is covered is fully covered is fully covered by at least one sensor so that there has to each and every point in that particular area has to be within the sensing range of at least one sensor so there is an alight terminology which is called the connectivity and connectivity of the nodes is basically to ensure that all nodes that means each and every node in the network from that point to the sink node there is some path that is available to transmit the sensed information so we have to ensure in the connective connectivity problem we have to ensure that all the nodes are connected in the network so that the sense data can be reach the sink node sensor coverage basically studies how to deploy or activate sensors to cover the monitoring area so there are two variants of this particular problem one is called the sensor placement problem and the other one is the density control so basically we have to ensure that how we are going to deploy the sensor nodes in a particular region of interest so that the problem of coverage is addressed so how do we place the sensor nodes and the second problem is that minimally how do we place so that you know appropriate or desirable density is maintained in the ah in that particular area so there are two modes of ah sensors one is the static sensor the other one is mobile sensor the problem of coverage with static sensors basically is different from the problem of coverage with mobile sensors whereas in static sensors we are primarily concerned about how to deploy the sensor so that each and every point in the area is covered in mobile sensors we have to ensure that with respect to not only space as in static sensor but also with respect to time that means spatio temporally that region of interest is covered with respect to space and time and that is in harder problem to solve now let us try to understand few concepts the first is the concept of sensing range and transmission range so when we have a node like this it can sense up to a certain radius around it so it is typically like few meters or so so for a particular sensor node the sensing radius is the sphere around it till which this particular node this particular node can sense so this is the sphere we are

talking about or in two d it is a circle now there is this allied concept of transmission range which is bit different so this transmission range or the communication range is concerned about how far this particular node can communicate so these are concentric circles and typically the sensing range is lower than is lesser than the communication range as shown in this particular figure but in literature on coverage you will often find that the sensing range and the communication range are equated they are considered to be equal so there is a relationship between the coverage and connectivity if the transmission range is greater than or equal to twice the sensing range it has been shown by researchers that the problem of coverage implies the problem of connectivity in other words we simply have to take care of coverage and if we have ensured that coverage has been taken care of in a particular area then automatically connectivity is also taken care of so for ensuring coverage as well as connectivity we have to ensure that for the particular sensor node that we are considering the transmission range is at least twice the sensing range and typically for most of the available sensor nodes in the market most of the ah you know so so this particular condition is taken care of so typically the the the transmission range or the communication range is quite ah ah much much bigger than the sensing range and that is why coverage becomes the main issue to be addressed so the problem of coverage once again ensures that how well the sensing field is monitored or tracked by the different sensors and to determine that with respect to certain application specific performance criteria in the case of static sensors where to deploy and or activate them and in case of mobile sensors how to plan the trajectory of the sensors so these two cases are collectively termed as the coverage problem in wireless sensor networks so we have the coverage problem for static sensor networks concerned mostly about how to place the sensors or if they are already placed how to activate them when and how to activate them so this is the problem of coverage for static sensors the problem of coverage for mobile sensors is basically how to plan the trajectory of these mobile sensors so that the region of interest is covered spatiotemporaly so the purpose of deploying a sensor network is to collect relevant data for processing or reporting and there are two types of reporting one is event driven the other one is on demand even driven ah applications include like forest fire monitoring building fire monitoring and so on so whenever there is some kind of event ah so event means like fire taking place that is an event ok so then ah that particular event is reported and on demand is basically that ah for example if there is a if there is some information that is required ah then ah that ah ah you know some query is going to be sent ah for example in inventory control systems so query is sent whenever there is some ah information that is required so the objective is to use a minimum number of sensors and maximize the network lifetime and network lifetime is basically in plain and simple terms it is about how long the network is going to survive how long the network is going to survive so actually in the literature there are different definitions of network lifetime ah so one definition basically says that the time until which the first sensor node in the network dies there is another definition which says that the time until which the last sensor node in the network dies that means it runs out of battery power or it you know it stops functioning and there is there are different other definitions as well which are somewhere in between so the time until which let us say p percentage of sensors die in a particular network is the network lifetime so basically the objective is to use a minimum number of sensors and maximize the network lifetime so this coverage problem is such that it can be addressed either using centralized algorithms or using distributed algorithms or using localized algorithms in distributed

version of the problem the nodes basically compute their position by communicating with their neighbors only ok every node basically computes their position by communicating only with their neighbors in the decentralized version the data are collected at the central point and global map is computed and in the localized version here basically it is sort of like a distributed algorithm where only a subset of the nodes in the sensor network participate in sensing communication and computation so it says sort of like a variant of the distributed algorithm localized algorithm so the different ways in which the sensors can be deployed for the purpose is basically either using deterministic means like you know you pre plan everything in a particular area you know that xyz coordinates where each of these individual sensor nodes are going to be deployed and that is pd determined p calculated and the other one is basically random where using some random means like airborne means or whatever the sensors are thrown into that particular area so there are two types of ranges one is the sensing range and the other one is the communication range and the objective of the problem is to maximize the network lifetime or minimize the number of sensors there are basically mostly three types of coverage that are quite common one is the area coverage the second is the point coverage and the third is the barrier coverage so area coverage out of these three is the most common form of coverage in area coverage what has to be done is we have to ensure that each and every point in a particular area is within the sensing range of at least one sensor node and that is that area covered so likewise actually that entire area is it consists of infinite number of points so we have to ensure that those infinite number of points each and [eve/every] every point in a particular area is within the sensing range of at least one sensor node and on area coverage lot of work has been done by zhang ahd hou hou proved that if the communication range is rc and the sensing range is rs then if the condition rc greater than equal to twice of rs holds then coverage implies connectivity and this is something that i told at the outset as well of this lecture so this is what has to be done so what basically has to be done is we have to ensure that two discs intersecting at crossings will be determent and then we have to ensure that likewise there are you know all these crossings that are formed out of the intersection of the different circles are covered and this is what the algorithm one of the algorithms that was proposed by zhang and hou the ogdc algorithm that we going to ah talk about shortly ah basically does and you know so without going into the details of it it me also explain the concept of point coverage so in point coverage what we are doing is we are ensuring that if there is a set of points in a particular area to ensure that those set of points are covered those set of points are covered in that particular area with minimal number of sensor nodes so it comes in two flavors one is the random point coverage and the other one is the deterministic point coverage in random point coverage it is required to distribute the sensors randomly so that every point must be covered by at least one sensor at all times and in deterministic point coverage we have to do essentially the same thing in a deterministic manner then we have the barrier coverage in barrier coverage we have three variants one is the one barrier coverage the second is the two barrier coverage and the third is the k barrier coverage so here we have to ensure that a particular barrier is covered so let me just explain to you this particular concept let us say that we have two countries let us say that we have two countries and we have this is country one and this is country two so this let us assume is the border between these two countries so the barrier coverage problem says that how we are going to place the sensor nodes and at what interval we are going to place them so that this particular barrier

is covered covered means what that let us say that if there is some intruder that gets into from country one it tries to get into country two then it will get detected by at least one sensor node so this is the barrier coverage problem so one barrier coverage ensures that at least one sensor node detects the intruder in what i just explained before two barrier coverage ensures that you know at least two sensors detect such an intrusion and k barrier coverage ensures that at least k number of sensors k can be anything greater than two k number of sensors basically detect this particular intrusion so we have different types of barrier coverage the left hand figure shows thus case of weak coverage and the right hand side figure shows the case of strong coverage so as you can see over here in this scenario we have weak coverage because you know one can find paths by which one can you know avoid getting sensed avoid getting sensed on the other hand if you look at over here there is no such paths that can be found without getting detected without the intruder getting detected by one of these sensor nodes so in this particular figure what we see is that these empty circles basically denoting the nodes which are there but an not active and these shaded circles denoting the nodes which are active so i hope that this point is clear over here so we have weak coverage and we have strong coverage so as you can see over here so a path like this by an intruder can avoid getting detected by add at least one sensor node however no such path can found out over here so this is the case of strong coverage and this is the case of weak coverage so what is required is to continuously ensure that the coverage criterion is mate at all points of time and we have to activate the nodes in that manner maybe if it is a random deployment there could be some redundant nodes and it there is no point of two nodes doing the same thing at the same time so maybe you put one node to the slip state the other one could be active and then this cycle can be changed over time so a region like this has to be covered so in this particular region we have these different sensors we have these different sensors so we have to ensure that we have to ensure that each and every point is covered so how do we do that we keep on placing this sensor nodes and let us say that this is the sensing range of this node this is the sensing range of the second node and this is the sensing range of the third node so these points that are shown over here are termed as the crossings these points and these points what is the difference over here these points are crossings between two circles two or more circles whereas these points are crossing between a circle and the boundary so we have one two three and four four crossings so a continuous region r is covered if there exists crossings in r and every crossing in r is covered so we have to ensure that there are crossing in this particular region and we do see that there a crossings in this region and then we have to ensure that every crossing like this crossing this crossing this crossing each and every crossing again has to be covered like this crossing ah in this particular figure is not covered this crossing is not covered whereas this particular crossing which was formed out of these two circles is covered by this circle so this crossing is covered whereas this crossing this crossing or these

crossing these are not covered so this is what has to be ensured and this is shown in a different way in this particular diagram so now let us look at a little bit of geometry so you know we have to come up with some optimality conditions optimality conditions for minimizing the overlap while covering the crossings and that way we have to ensure that minimum number of sensor nodes are utilized in order to cover covered the crossings so if nodes a and b are fixed like in this particular figure so if nodes a and b are fixed we have to place a nodes c we have to place a node c in such a way that o are equal to oq so a b we have to place c in such a way that or sorry o or equal to oq ok if nodes a b and c all can change their locations then and that is quite possible so if nodes a b and c all can change their locations then we can even have op equal to or equal to oq right so op equal to or equal to oq that can be very well done and if all nodes have the same sensing range that means the circles have the same radius then the distance between them is square root of three times rs the sensing range so a node in the ogdc algorithm what happeneds is first a node volunteers as a starting node and it starts broadcasting a message containing the ideal direction which is randomly selected if another node b which is closest to the ideal distance and angle becomes active a node c covering p and closest to the optimal location becomes active and repeatedly it is required to cover the crossings uncovered crossings with notes that incur minimum overlap so a node sleeps if its coverage area is completely covered so let me show you this particular concept it to really so what we have we have one node we have another node both have the same radius right so and these are the crossings this is one crossing and this is another crossing so the point that was made earlier was that we have to place this another node in such a way sorry this is not correct so we have to place it in this way ok not this in such a way that this this this is again let me let me do it once again so let us say that we have two different nodes and we have to place third node in such a way that this one this one and this one at the same so in this diagram actually it is not very precise so we have to do it in such a way op or oq so op equal to or equal to oq so what happens is that one node what it will do it will at a particular angle it will start broadcasting a message ok then another node which is in this particular direction and in this angle that means in this particular direction and is closest to this particular node that node has to be placed in this manner ok and like this if you consider this whole area you keep on doing the same thing and ensure that the crossings are also covered so what is going to happen like this you know so what we are going to get is all the crossings getting covered like this with a minimum number of sensor nodes ok so this is how the ogdc algorithm works so node x starts the process it selects the

first node y at a distance some distance from this particular node so this distance is what square root of three times rs square root of three times rs it will choose this node then this node z is selected at a distance square root of three times rs from both x and y so from both x and y this has to be put square root of rs distance square root of three times rs distance so this is square root of three times rs this is square root of three times rs and this is square root of three times rs so let us go through this algorithm once again each node voluntarily participates with probability p in this case this node a participates with probability p it chooses a back of time randomly if it does not hear anything from its neighbors it declares itself as a starting node it declares its position and preferred direction so in this case it declares its current position and the direction alpha on receiving messages from the starting node each node computes the deviation from the desired position it chooses a back off time randomly when the back off time expires it sense the power on message then it declares its position and the preferred direction the process continues until the entire area is covered as in this particular figure right so this node it started at a particular angle closest to it another node is chosen this particular node basically ah ah will be selected these crossings are formed another node c is chosen so square root of three times rs square root of three times rs square root of three times rs and then we have further crossings so you keep on placing the other nodes so that all the crossings are covered so some highlights again a node initiates the process with the desired distance and angle other nodes calculate the deviation and the optimal one is chosen the process continues for all nodes and all cover nodes go to the sleep mode this process is continued for each round so with this we come to an end of the lecture on ah coverage and coverage is one of the very important issues in sensor networks because it ensures that each and every point ah ah in the region of interest is covered or a set of points is covered and if it is each and every point is covered that is that area coverage problem and if it is a set of points that have to be covered then its a point coverage problem and it is this area coverage problem that is the most common and most popular form of coverage problem that is ah addressed ah ah ah in the literature lot of research works have been gone into it similarly there is the third type of coverage which is the barrier coverage here again ah ah you know this is also very important because sensor networks are often used for unmans surveillance in ah you know bordering areas between two countries and that is where ah you know ah this particular rectangular strip or a strip of ah region between two countries has to be monitored using sensors so the coverage while ensuring that minimum number of sensor nodes are used at and has to be placed in that particular border is a very important problem and is known as the problem of barrier coverage and we have finally discussed the ah ogdc algorithm which is one of the important ah area coverage algorithms that have been proposed and is quite popularly used in the sensor networks community thank you