## Contributed Session Mon.2.H 3002

#### Monday, 13:15 - 14:45 h, Room: H 3002

**Cluster 23: Telecommunications & networks** [...]

### Wireless networks

**Chair: AndrĂ© Berger**

**Monday, 13:15 - 13:40 h, Room: H 3002, Talk 1**

**Sergey Astrakov**

The full efficient monitoring of stripe with external deployment sensors

**Abstract:**

We are considering a problem for min-density covering of a stripe in wireless sensor networks. There is the special condition for networks such as sensor unit not located in area of stripe. Since energy consumption of sensing is proportional to the coverage space, a problem of power efficient sensing of a plane region could be reduced to the problem of search min-density covering of a region within disks with adjustable sensing ranges. We studied several new efficient regular models of covering and have offered a general classification.

%Key words: wireless sensor networks, power efficient sensing, density covering

**Monday, 13:45 - 14:10 h, Room: H 3002, Talk 2**

**Ashutosh Nigam**

A Lagrangian heuristic for delay constrained relay node placement problem in wireless sensor networks

**Coauthor: Yogesh K. Agarwal**

**Abstract:**

The Optimal Delay Constrained Relay Node Placement problem is stated as: given the locations of the root node, a set of source nodes and a set of candidate relay nodes and delays provided on each possible links (edges), find a minimal set of relay nodes amongst the candidate relay nodes such that there is a path, within the specified delay bound, between each source node and the root node via the selected relay nodes only. In our work, we propose an algorithm which uses the constrained shortest path using Dijkstra and Lagrangian heuristic. The proposed polynomial time algorithm (complexity *O(n*log(d*_{max}/m), where *n* is the number of candidate relay nodes, *m* is the number of edges and *d*_{max} is the pre-specified delay bound)provides close to optimal solution (in most of the cases the optimality gap is within 10%). We also compare our algorithm with other existing polynomial time algorithms and demonstrate the efficiency of our algorithm in terms of solution strength as well as the CPU Time.

**Monday, 14:15 - 14:40 h, Room: H 3002, Talk 3**

**AndrĂ© Berger**

Constrained resource assignments: Fast algorithms and applications in wireless networks

**Coauthors: James Gross, Tobias Harks, Simon Tenbusch**

**Abstract:**

Resource assignment problems occur in a vast variety of applications, from scheduling problems over image recognition to communication networks, just to name a few. While in some of the applications an assignment of the resources may be needed only once, often the assignment has to be computed more often for different scenarios. In that case it is essential that the assignments can be computed very fast. Moreover, implementing different assignments in different scenarios may come with a certain cost for the reconfiguration of the system.

In this paper we consider the problem of determining optimal assignments sequentially over a given time horizon, where consecutive assignments are coupled by constraints which control the cost of reconfiguration. We develop fast approximation and online algorithms for this problem with provable approximation guarantees and competitive ratios.

Finally, we establish the applicability of our model and our algorithms in the context of OFDMA wireless networks, finding a significant performance improvement for the total bandwidth of the system using our algorithms.