Grid spanners with low forwarding index for energy efficient networks

详细信息    查看全文

• 作者：Frederic Giroire^a ; ^{frederic.giroire@cnrs.fr" class="auth_mail" title="E-mail the corresponding author} ; Stephane Perennes^a ; Issam Tahiri^b
• 关键词：spanning subgraphs ; forwarding index ; energy saving ; routing ; grid
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2016
• 出版时间：June 2016
• 年：2016
• 卷：52
• 期：Complete
• 页码：141-148
• 全文大小：265 K

文摘

A routing m>Rm> of a connected graph m>Gm> is a collection that contains simple paths connecting every ordered pair of vertices in m>Gm>. The m>edge-forwarding index with respect to Rm> (or simply the forwarding index with respect to m>R  m>) mmlsi1" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316300245&_mathId=si1.gif&_user=111111111&_pii=S1571065316300245&_rdoc=1&_issn=15710653&md5=6d3dd83515fadb52c9799b2209b52255" title="Click to view the MathML source">π(G,R)mathContainer hidden">mathCode"><math altimg="si1.gif" overflow="scroll"><mi>πmi><mo stretchy="false">(mo><mi>Gmi><mo>,mo><mi>Rmi><mo stretchy="false">)mo>math> of m>Gm> is the maximum number of paths in m>Rm> passing through any edge of m>Gm>. The m>forwarding index  m>mmlsi2" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316300245&_mathId=si2.gif&_user=111111111&_pii=S1571065316300245&_rdoc=1&_issn=15710653&md5=5c5dc46533d06d01764ac89b796dd5be" title="Click to view the MathML source">π(G)mathContainer hidden">mathCode"><math altimg="si2.gif" overflow="scroll"><mi>πmi><mo stretchy="false">(mo><mi>Gmi><mo stretchy="false">)mo>math> of m>G  m> is the minimum mmlsi1" class="mathmlsrc">mulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S1571065316300245&_mathId=si1.gif&_user=111111111&_pii=S1571065316300245&_rdoc=1&_issn=15710653&md5=6d3dd83515fadb52c9799b2209b52255" title="Click to view the MathML source">π(G,R)mathContainer hidden">mathCode"><math altimg="si1.gif" overflow="scroll"><mi>πmi><mo stretchy="false">(mo><mi>Gmi><mo>,mo><mi>Rmi><mo stretchy="false">)mo>math> over all routings m>Rm>'s of m>Gm>. This parameter has been studied for different graph classes [Xu, J.-M. and M. Xu, m>The forwarding indices of graphs – a surveym>, CoRR abs/1204.2604 (2012)], [Bouabdallah, A. and D. Sotteau, On the edge forwarding index problem for small graphs, m>Networksm>23 (1993), pp. 249–255], [Fernandez de la Vega, W. and L. M. Gordones, m>The forwarding indices of random graphsm>, Random Structures and Algorithms 3 (1992), pp. 107–116], [de la Vega, W. F. and Y. Manoussakis, m>The forwarding index of communication networks with given connectivitym>, Discrete Appl. Math. 37–38 (1992), pp. 147–155]. Motivated by energy efficiency, we look, for different numbers of edges, at the best spanning graphs of a square grid, namely those with a low forwarding index.