Đồ thị định tuyến khác được xem xét trong tài liệu là đồ thị Delaunay hạn chế [Gao et và đồ thị Yao Li et Bảng dưới đây tóm tắt các yếu tố căng sức mạnh và mức độ nút tối đa của các đồ thị định tuyến, giả sử α = 2 | 5th ACM MobiHoc - Tokyo May 24 2004 RNG GG and other routing graphs 2 Other routing graphs considered in the literature are the Restricted Delaunay Graph Gao et and the Yao Graph Li et The table below summarizes the power stretch factor and maximum node degree of these routing graphs assuming a 2 Power Degree RNG n-1 n-1 GG 1 n-1 RDG 0 n YG n-1 Remark 1 the Gabriel Graph has optimal power stretch factor Remark 2 all the routing graphs above are sparse . constant average node degree but have maximum node degree linear in n Istituto di Informatica e Telematica Energy-efficient communication 5 7 5th ACM MobiHoc - Tokyo May 24 2004 Energy-efficient broadcast Other problem considered in the literature determination of energyefficient broadcast graphs Similarly to the case of unicast the concept of broadcast stretch factor of a subgraph G of G can be defined Also in this case the goal is to find sparse broadcast spanners that can be computed in a distributed and localized fashion Unfortunately this task is more difficult than in the case of unicast Istituto di Informatica e Telematica Energy-efficient communication 6 7 5th ACM MobiHoc - Tokyo May 24 2004 Energy-efficient broadcast 2 Cagali et and Liang02 the task of finding the energy-optimal broadcast tree rooted at an arbitrary node u of G is NP-hard Wieselthier et the authors introduce three greedy heuristics for the minimum-power broadcast problem based on the construction of the MST Wan et it is proved that the broadcast stretch factor of the MST is c for some 6 c 12 Unfortunately the MST cannot be computed using only local information Open problem no distributed and localized algorithm that constructs a broadcast spanner is known Istituto di Informatica e Telematica Energy-efficient communication 7
