无线Ad Hoc网络中每包延迟精确分解技术

38 浏览量更新于2024-08-26 收藏 2.04MB PDF 举报

本文主要探讨了无线Ad Hoc网络中精确每包延迟层析成像（Per-PacketDelay Tomography, PPDT）的问题，这是在多跳无线自组网（Wireless Ad Hoc Networks, WANETs）环境中一项关键的研究工作。作者Yi Gao、Wei Dong、Chun Chen、Xiaoyu Zhang、Jiajun Bu和Xue Liu作为IEEE和ACM的会员，提出了一个名为Domo的创新方法，旨在提高网络可见性，提升网络测量与管理效率。传统的网络延迟分析通常关注端到端（End-to-End）的延迟，但在复杂的WANETs中，了解每跳（Per-Hop）的延迟对于优化路径选择、故障定位和流量控制至关重要。Domo的方法是被动的、轻量级且具有高度准确性，它通过在每个数据包中附加较小的开销，收集必要的时延约束信息。在无线网络层面，Domo设计了一套优化问题，考虑了不同时间量之间的复杂关系。作者将每包延迟层析成像问题转化为一组优化问题，并在接收端（PC side）利用半定义松弛（Semi-Definite Relaxation, SDR）技术来求解。SDR是一种数学工具，允许非线性优化问题转化为更易于处理的线性矩阵形式。通过这种方式，Domo能够有效地估计出每跳的延迟值，从而实现对网络内部延迟结构的精确解析。这个解决方案的优势在于其无需主动干预网络操作，降低了对网络性能的影响，并能在保证精度的同时降低实施成本。这对于网络监控、诊断网络瓶颈和进行实时性能优化具有显著的价值。此外，通过每包延迟的精细分析，可以为流量工程、路由算法优化和QoS保证提供更精确的数据支持。该论文深入研究了无线Ad Hoc网络中的精确每包延迟层析成像技术，提出了一种创新的解决方案Domo，对于提高网络性能管理和测量具有重要的理论和实践意义。通过解决网络侧的优化问题和利用先进的数学工具，Domo展示了在实际应用中实现高效、准确网络延迟分解的可行性。

482 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 25, NO. 1, FEBRUARY 2017

delay of a link or a path, in a coordinated streaming environ-

ment. RLI [17] obtains per-ﬂow delay by performing linear

interpolation based on the data collected from the reference

packets being injected to the sender. Besides the end-to-end

delay measurement approaches, there are also approaches

aiming at reconstructing per-hop delay. A recent work [9]

proposes a very effective algorithm to reconstruct additive link

metrics (e.g., delay) by path measurements. It assumes the link

metrics are constant during the measurement, which is not the

case in wireless ad-hoc networks. Another work [18] measures

and analyzes the single-hop packet delay on an IP backbone

network. It requires global clock synchronization for all routers

in the networks. These works cannot be directly adopted to

wireless ad-hoc networks due to several reasons, such as the

constrained resource and the lack of global synchronization.

Domo overcomes this difﬁculty by performing per-hop per-

packet delay reconstruction. At the meantime, Domo does

not depend on synchronized global clock, which is usually

not available in wireless ad-hoc networks [7] due to its high

message and energy overhead.

B. Delay Measurement in Wireless Ad-Hoc Network

End-to-End Delay: In wireless ad-hoc networks, there

are several recent works [6], [7] focusing on recording

the end-to-end delay of each collected packet at the sink.

Wang et al. [7] propose to timestamp packets at the MAC layer

to precisely record packet sending/receiving. Then the packet

sojourn time at each hop can be accumulated and recorded in

a particular ﬁeld in the packet. When the packet reaches the

sink, that ﬁeld will store the whole end-to-end delay. Different

from these approaches, Domo aims at reconstructing more

ﬁne-grained delay, i,e., per-hop per-packet delay.

Per-Hop Delay: There are also several approaches [15], [16]

related to ﬁne-grained delay reconstruction in wireless ad-hoc

networks. MNT [15] is the state-of-the-art approach to recon-

struct per-hop packet arrival order in sensor networks. For each

packet p, MNT is able to infer the two local packets right

before and after packet p at each hop. Since the generation

time of each local packet is known, the per-hop delay of

the packet p can be bounded by the two corresponding local

packets at each hop. Further, the bounds can be improved by

correlating information from packets passing through the same

forwarding nodes as packet p. The delay estimation accuracy

of MNT mainly depends on the number of packets passing

through each forwarding node per unit time, which further

mainly depends on the inter-packet interval (IPI). Therefore,

increasing the timestamping granularity of MNT cannot

improve the delay estimation accuracy. MessageTracing [16]

records every packet sent and received into the local storage

of each node. It does not reconstruct per-hop per-packet delay

directly. However, by the information it records, we can infer

the order of many packet sending/receiving events. From the

perspective of revealing the internal behaviors of the networks,

MessageTracing provides another possible method (i.e., local

logging). In the evaluation section, we will show that Domo

signiﬁcantly outperforms these related approaches in terms of

the reconstruction accuracy.

III. N

ETWORK MODEL

In this section, we give the network model of this work.

We also summarize the assumptions made and notations used

in Domo. We assume that Domo works in a wireless ad-hoc

network running data collection task to a single sink node.

Each node generates and sends data packets periodically to the

sink. All nodes in the network can forward packets for other

nodes. The network includes common phenomena in wireless

ad-hoc networks such as routing dynamics, packet loss and no

global timing information.

A. Modeling

FIFO Send Queue: Each node includes an FIFO send

queue for all outgoing packets. This queue keeps the packets

generated by the node as well as packets to be forwarded. The

node will keep sending the same packet at the queue head till

a successful acknowledgement or the maximum number of

retransmission is reached. FIFO send queue is widely used

in routing protocols (e.g., CTP [19], MiniRoute) for wireless

ad-hoc networks. Note that the FIFO send queue does not

guarantee that the packet arrival order at sink is the same as the

packet arrival order at each node. In fact, existing works [15]

have shown that packets could be reordered in the network

due to the dynamic routing in sensor networks.

Routing Path Information: Since the wireless network topol-

ogy is usually dynamic. Per-hop delays are only useful when

the packet path is already known. Thanks to the recent progress

in path reconstruction [15], [20], [21], we are able to recon-

struct the packet path with small overhead, even in large scale

networks with hundreds of nodes. For example, a recent path

reconstruction approach Pathﬁnder [20] achieves above 96%

path reconstruction ratio in a network with 900 nodes. In case

of imperfect path information, i.e., the routing paths of some

received packets cannot be recovered, the per-hop delays

of those packets are not deﬁned. In fact, a packet with-

out routing path information is viewed as a lost packet in

Domo. As we will show in the evaluation, Domo is able

to achieve satisfactory performance even with severe packet

losses.

Node Delay: Since wireless signal propagates very fast in

the air, a packet delay from the source to the sink actually

consists of the sojourn times the packet stays on the source

node and all forwarding nodes. The sojourn time is the time

between the node’s radio starts to receive the packet and starts

to transmit the packet. Since the time a node starts to transmit

a packet is very close to the time the next hop starts to receive

the packet. In the rest of this paper, we will use the difference

between the time a node A starts to receive a packet and the

time the next hop B starts to receive the packet to be the

node delay of this packet at node A. The sojourn time at

each node can be measured accurately on that node. In the

implementation section, we will give a detailed description of

measuring the node delay at that node.

End-to-End Delay: Recent works [6], [7] show that the

end-to-end delay can be obtained accurately after a packet

reaches the sink. MAC layer timestamping technique is used

to record the actual time a packet is transmitted by the radio

剩余11页未读，继续阅读

weixin_38727980

粉丝: 3
资源: 931

无线Ad Hoc网络中每包延迟精确分解技术

论文研究-无线Ad hoc网络中的丢包分析模型研究.pdf

无线自组网中的精确每包延迟层析成像

无线Adhoc网络技术.doc

opnet:adhoc网络

ad hoc网络与ZigBee网络的区别

基于adhoc的网络协议

陈林星 adhoc网络 pdf csdn

基于IEEE 802.11标准的AdHoc网络架构

在无线Ad hoc网络中，如何设计一个高效的分布式全双工链路调度算法，以提升网络吞吐量并降低时延？

移动Ad Hoc网络的特点有哪些

最新资源