Sensor Networks Assignment 3 Hints

From Ece

Hashing A String Into X,Y Coordinates

Here is a really simple way to hash any string value into a list of x and y coordinates. Note: width and height are the maximum x and y values you want returned.

  def hashStringToCoord(self, s, width, height):        
       random.seed(hash(s))         
       return [random.random()*width, random.random()*height]

It is ok to use random() here because you seed it right before you use it. Since you seed the random number generator with the hash value of the string, you will always get the same result for a given string, which is required by the geographic hash table algorithm.

Another Way to Hash Coordinates

Here is another way you could hash a key value to x,y coordinates. I just concatenated the same string again to get a different digest for the y value:

   def hashCoords(self, s, xmax, ymax):
       m = md5.new(s)
       x = m.hexdigest()
       m.update(s)
       y = m.hexdigest()
       return[int(x, 16) % xmax, int(y, 16) % ymax]

My main reason for posting this was to ask how you are implementing the perimeter search. I am hung up on how to tell when you are at the node that is closest to the hashed value. Do you have to go around the perimeter twice and keep a list of nodes traversed? Someone who has this done, let me know. Thanks. ~Terry

Terry, I implemented my perimeter search by always forwarding packets to the node which has the smallest angle returned by the function getAngle() (see below). In the payload of the message i have a list of node id's with their corresponding distances to the destination cordinate. Once i have made a complete loop around the destination (my node id appears twice in the list), I check to see if my distance to the destination is the smallest one listed for all nodes on the perimiter of the destination. If i am the closest node, then i am the host for that data, if i am not the closest node, then i am a replica (mirror) for that data. Hope that helped -Craig

Calculating Angles With Respect To A Given Destination Coordinate

I know my explanation in class on how to calculate angles was kind of confusing, so i thought i would give an example. Note: the following code assumes that the coordinate (0,0) is in the upper left. If it is in the lower left then remove the -1 in the getPositiveDegrees() function.

   def getPositiveDegrees(self, start, dest):
       theta = -1 * math.degrees(math.atan2(dest[1] - start[1], dest[0] - start[0])) + 360
       return (theta % 360)
       
       
   def getAngle(self, startCoord, destCoord, neighborCoord):
       offset = self.getPositiveDegrees(startCoord, destCoord)
       theta  = self.getPositiveDegrees(startCoord, neighborCoord)
       return ((360 - (offset - theta)) % 360)

The input parameters are lists which contain two elements, x and y. Calling getAngle() will produce an angle between 0 and 360 degrees. To find the appropriate neighbor node to forward a message too, simply find the neighbor node with the smallest angle returned by getAngle(). You could save some computation time and "power" by keeping everything in radians, but understanding this algorithm is hard enough, so i think degrees are appropriate.