Multi-Hop Routing and Scheduling in Wireless Networks in the SINR model

Details Multi-Hop Routing and Scheduling in Wireless Networks in the SINR model Multi-Hop Routing and Scheduling in Wireless Networks in the SINR model

2011-04-07

arxiv.org/abs/1104.1330v5

Computer Science

Data Structures and Algorithms

Scientific paper

We present an algorithm for multi-hop routing and scheduling of requests in wireless networks in the \sinr\ model. The goal of our algorithm is to maximize the throughput or maximize the minimum ratio between the flow and the demand. Our algorithm partitions the links into buckets. Every bucket consists of a set of links that have nearly equivalent reception powers. We denote the number of nonempty buckets by $\sigdiv$. Our algorithm obtains an approximation ratio of $O(\sigdiv \cdot \log n)$, where $n$ denotes the number of nodes. For the case of linear powers $\sigdiv =1$, hence the approximation ratio of the algorithm is $O(\log n)$. This is the first practical approximation algorithm for linear powers with an approximation ratio that depends only on $n$ (and not on the max-to-min distance ratio). If the transmission power of each link is part of the input (and arbitrary), then $\sigdiv = O(\log\Gamma + \log \Delta)$, where $\Gamma$ denotes the ratio of the max-to-min power, and $\Delta$ denotes the ratio of the max-to-min distance. Hence, the approximation ratio is $O(\log n \cdot (\log\Gamma + \log \Delta))$. Finally, we consider the case that the algorithm needs to assign powers to each link in a range $[\pmin,\pmax]$. An extension of the algorithm to this case achieves an approximation ratio of $O[(\log n + \log \log \Gamma) \cdot (\log\Gamma + \log \Delta)]$.

Affiliated with

Also associated with

No associations

Rating

Multi-Hop Routing and Scheduling in Wireless Networks in the SINR model does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Multi-Hop Routing and Scheduling in Wireless Networks in the SINR model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-Hop Routing and Scheduling in Wireless Networks in the SINR model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-717975