Search Constraints

Start Over
Filtering by: Creator Krizanc, Danny Remove constraint Creator: Krizanc, Danny Creator Narayanan, Lata Remove constraint Creator: Narayanan, Lata

Search Results

  • On minimizing the sum of sensor movements for barrier coverage of a line segment

    Resource Type:
    Conference Proceeding
    Creator:
    Czyzowicz, Jurek, Opatrny, Jaroslav, Kranakis, Evangelos, Narayanan, Lata, Krizanc, Danny, Stacho, Ladislav, Urrutia, Jorge, Yazdani, Mohammadreza, and Lambadaris, Ioannis
    Abstract:
    A set of sensors establishes barrier coverage of a given line segment if every point of the segment is within the sensing range of a sensor. Given a line segment I, n mobile sensors in arbitrary initial positions on the line (not necessarily inside I) and the sensing ranges of the sensors, we are interested in finding final positions of sensors which establish a barrier coverage of I so that the sum of the distances traveled by all sensors from initial to final positions is minimized. It is shown that the problem is NP complete even to approximate up to constant factor when the sensors may have different sensing ranges. When the sensors have an identical sensing range we give several efficient algorithms to calculate the final destinations so that the sensors either establish a barrier coverage or maximize the coverage of the segment if complete coverage is not feasible while at the same time the sum of the distances traveled by all sensors is minimized. Some open problems are also mentioned.
    Date Created:
    2010-12-13

  • Routing on delay tolerant sensor networks

    Resource Type:
    Conference Proceeding
    Creator:
    Kranakis, Evangelos, Krizanc, Danny, Narayanan, Lata, and Keane, Michael
    Abstract:
    Delay (or disruption) tolerant sensor networks may be modeled as Markovian evolving graphs [1]. We present experimental evidence showing that considering multiple (possibly not shortest) paths instead of one fixed (greedy) path can decrease the expected time to deliver a packet on such a network by as much as 65 per cent depending on the probability that an edge exists in a given time interval. We provide theoretical justification for this result by studying a special case of the Markovian evolving grid graph. We analyze a natural algorithm for routing on such networks and show that it is possible to improve the expected time of delivery by up to a factor of two depending upon the probability of an edge being up during a time step and the relative positions of the source and destination. Furthermore we show that this is optimal, i.e., no other algorithm can achieve a better expected running time. As an aside, our results give high probability bounds for Knuth's toilet paper problem [11].
    Date Created:
    2009-12-01