Strong connectivity of sensor networks with double antennae

详细信息    查看全文

• 作者：Mohsen Eftekhari^a ; ^{m_eftek@encs.concordia.ca" class="auth_mail" title="E-mail the corresponding author} ; Evangelos Kranakis^c ; ¹ ; ^{kranakis@scs.carleton.ca" class="auth_mail" title="E-mail the corresponding author} ; Fraser MacQuarrie^b ; ^{frasermacquarrie@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Oscar Morales-Ponce^b ; ² ; ^{oscarmponce@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Lata Narayanan^a ; ³ ; ^{lata@cs.concordia.ca" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Connectivity ; Double antenna ; Range ; Stretch factor ; Unit disk graph
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：11 January 2016
• 年：2016
• 卷：610
• 期：part_PB
• 页码：192-203
• 全文大小：491 K

文摘

Inspired by the well-known Dipole and Yagi antennae we introduce and study a new theoretical model of directional antennae that we call double antennae. Given a set P of n sensors in the plane equipped with double antennae (with either dipole-like or Yagi-like propagation patterns) of angle ϕ, we study the connectivity and stretch factor   problems, namely finding the minimum range such that there exists an orientation of the double antennae of that range that guarantees strong connectivity or stretch factor of the resulting network. We introduce the new concepts of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515001140&_mathId=si1.gif&_user=111111111&_pii=S0304397515001140&_rdoc=1&_issn=03043975&md5=0336d5a926a7e2a45cd42414b6a9a373" title="Click to view the MathML source">(2,ϕ)class="mathContainer hidden">class="mathCode">$(2,\varphi )$-connectivity and ϕ-angular range and use them to characterize the optimality of our algorithms. We prove that the ϕ-angular range is a lower bound on the range required for strong connectivity and show how to compute it in time polynomial in n  . We give an algorithm for orienting the antennae so as to attain strong connectivity using optimal range when class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515001140&_mathId=si15.gif&_user=111111111&_pii=S0304397515001140&_rdoc=1&_issn=03043975&md5=0ee309f78cfa124e91d199a387f993f5" title="Click to view the MathML source">ϕ≥3π/4class="mathContainer hidden">class="mathCode">$\varphi \ge 3\pi /4$ and an algorithm that approximates the range to class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515001140&_mathId=si3.gif&_user=111111111&_pii=S0304397515001140&_rdoc=1&_issn=03043975&md5=ff165ad5e0adebd845d2cdc8ffe4ef01">class="imgLazyJSB inlineImage" height="15" width="22" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515001140-si3.gif">class="mathContainer hidden">class="mathCode">$\sqrt{3}$ times the optimal range for class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515001140&_mathId=si264.gif&_user=111111111&_pii=S0304397515001140&_rdoc=1&_issn=03043975&md5=170be263718fe0eafde190d07e2559fa" title="Click to view the MathML source">ϕ≥π/2class="mathContainer hidden">class="mathCode">$\varphi \ge \pi /2$. For class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515001140&_mathId=si5.gif&_user=111111111&_pii=S0304397515001140&_rdoc=1&_issn=03043975&md5=38688d73e0920263311f281cc6644168" title="Click to view the MathML source">ϕ<π/3class="mathContainer hidden">class="mathCode">$\varphi <\pi /3$, we show that the problem is NP-complete to approximate within a factor class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515001140&_mathId=si3.gif&_user=111111111&_pii=S0304397515001140&_rdoc=1&_issn=03043975&md5=ff165ad5e0adebd845d2cdc8ffe4ef01">class="imgLazyJSB inlineImage" height="15" width="22" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515001140-si3.gif">class="mathContainer hidden">class="mathCode">$\sqrt{3}$. For class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515001140&_mathId=si264.gif&_user=111111111&_pii=S0304397515001140&_rdoc=1&_issn=03043975&md5=170be263718fe0eafde190d07e2559fa" title="Click to view the MathML source">ϕ≥π/2class="mathContainer hidden">class="mathCode">$\varphi \ge \pi /2$, we give an algorithm to orient the antennae so that the resulting connectivity network has a stretch factor of at most 4 compared to the underlying unit disk graph.