{"id":627,"date":"2008-11-30T05:33:33","date_gmt":"2008-11-30T05:33:33","guid":{"rendered":"http:\/\/network.ee.tsinghua.edu.cn\/niulab\/?p=627"},"modified":"2010-08-24T10:25:22","modified_gmt":"2010-08-24T10:25:22","slug":"non-preemptive-constrained-link-scheduling-in-wireless-mesh-networks","status":"publish","type":"post","link":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/?p=627","title":{"rendered":"Non-preemptive Constrained Link Scheduling in Wireless Mesh Networks"},"content":{"rendered":"<p><a href=\"http:\/\/network.ee.tsinghua.edu.cn\/papers\/globecom08_wuyq.pdf\" target=\"_blank\"><img loading=\"lazy\" decoding=\"async\" class=\"alignright size-full wp-image-117\" title=\"pdf\" src=\"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/wp-content\/uploads\/2010\/08\/pdf.gif\" alt=\"\" width=\"95\" height=\"50\" \/><\/a><br \/>\n<span class=\"paper_subtitle\">LANGUAGE<\/span><br \/>\nEnglish<br \/>\n<span class=\"paper_subtitle\">SOURCE<\/span><br \/>\nProc. of GLOBECOM 2008<br \/>\n<span class=\"paper_subtitle\">Published Date<\/span>:2008-11-30<br \/>\n<span class=\"paper_subtitle\">ABSTRACT<\/span><br \/>\nThis paper considers the problem of link scheduling with non-preemptive constraint in wireless mesh networks. In real-world implementation, there is often a constraint that a link can only transmit once and occupy consecutive time slots during a frame. We refer to it as the non-preemptive constraint. To date, only few scheduling algorithms in the literature has taken such constraint into consideration. In this paper, we show that optimal non-preemptive link scheduling (NPLS) problems are generally NP-hard and are provably harder to solve than link scheduling without such a constraint. To tackle the problem, a low-complexity list link scheduling (LLS) algorithm is proposed to approximate the optimal NPLS. Our analysis shows that with a randomly selected link-ordering list, throughput degradation of LLS compared to the optimal NPLS is bounded even in the worst case. By carefully constructing the link-ordering list, the performance of LLS can be further greatly improved. In this paper, we propose three schemes to construct link-ordering lists. The performance of the proposed schemes is evaluated through simulations.<\/p>\n","protected":false},"excerpt":{"rendered":"<p><a href=\"http:\/\/network.ee.tsinghua.edu.cn\/papers\/globecom08_wuyq.pdf\" target=\"_blank\"><img loading=\"lazy\" decoding=\"async\" class=\"alignleft size-full wp-image-117\" title=\"pdf\" src=\"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/wp-content\/uploads\/2010\/08\/pdf.gif\" alt=\"\" width=\"95\" height=\"50\" \/><\/a>Yiqun Wu, Ying Jun (Angela) Zhang, Zhisheng Niu, <span class=\"papertitle\">Non-preemptive Constrained Link Scheduling in Wireless Mesh Networks<\/span>, <span class=\"papersource\">Proc. of GLOBECOM 2008<\/span><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[7],"tags":[99,84,76,18],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/posts\/627"}],"collection":[{"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=627"}],"version-history":[{"count":2,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/posts\/627\/revisions"}],"predecessor-version":[{"id":795,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=\/wp\/v2\/posts\/627\/revisions\/795"}],"wp:attachment":[{"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=627"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=627"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/network.ee.tsinghua.edu.cn\/niulab\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=627"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}