基于OBDD的无线传感器网络 multicast 模型可靠性评估新算法
127 浏览量
更新于2024-07-14
收藏 2.83MB PDF 举报
本文献主要关注于无线传感器网络（Wireless Sensor Networks, WSN）的可靠性评估问题，特别是在组播模型下的解决方案。在信息技术领域，WSNs因其分布式、自组织和能量有限的特性，在环境监控、军事侦察、工业自动化等领域具有广泛应用。然而，WSNs的可靠性评估是一个复杂的问题，特别是当涉及到节点间的多路径通信和故障检测时，其计算复杂度被证明为NP-hard，即随着网络规模的增加，计算难度呈指数级增长。
该研究提出了一种新颖的基于Order-Bounded Decision Diagrams (OBDD) 的算法来解决这一挑战。OBDD是一种数据结构，用于高效地表示和操作布尔函数，特别适合处理大规模组合优化问题。在无线传感器网络的组播模型中，算法通过将复杂的网络状态空间转化为OBDD的形式，极大地减少了计算的复杂性。组播模型的优势在于它能够同时向多个接收节点发送数据，这在一定程度上减少了冗余通信，从而提高了整体的网络效率。
作者Zongshuai Yan, Chenhua Nie, Rongsheng Dong, Xi Gao 和 Jianming Liu 来自广西桂林电子科技大学计算机科学与工程学院以及中兴通讯股份有限公司，他们共同研究了如何利用OBDD技术对WSN的节点状态进行有效管理和分析，以便于评估网络在面对故障或异常情况时的可靠性和生存能力。他们的工作不仅提供了理论上的突破，也有可能为实际应用中的WSN设计和优化提供实用的工具。
论文在2014年7月16日首次接收，经过修订后于同年11月5日被接受发表，学术编辑为XueJun Li。该文章遵循Creative Commons Attribution License，允许无限制地使用、分发和复制，只要原文得到适当的引用。这项研究成果对于理解和提升无线传感器网络的可靠性评估具有重要的理论价值和实际意义，为未来相关领域的研究者提供了新的视角和方法。
Mathematical Problems in Engineering
() =(
1
,
2
,...,
𝑛
)is the set of target in the WSN on
the multicast model, where is the number of the
target and 2≤.
2.2. e Problem of WSN Reliability. In this paper, we studied
theinfrastructurecommunicationreliabilityofaWSN.Below
aretheassumptionsmadetoevaluatereliabilityinour
analysis:
() edges between two nodes are perfect;
() nodes failures are statistically independent;
() the fault-tolerant clustering protocol is executed to
keep the topology.
With the assumption that the links are imperfect, this type
of structure would rapidly increase the complexity in order to
compute the reliability of WSNs. In this study, we assume that
the links are perfect for the convenience of studying them;
however,ourfutureworkwillinvestigatetheevaluationof
WSN reliability with imperfect nodes as well as imperfect
links. Based on the above assumptions some denitions are
presented as follows.
Denition 1 (Reliability). e reliability is the probability that
the special elements will accomplish a required task within
a time threshold []. In this study, the reliability of a WSN
is an important measure in evaluating the performance of
aWSN.
Denition 2. e reliability of the WSN is the probability that
there exists an operational path between the sink node and
every node in the set of target nodes.
Denition 3. Given the WSN network = (,,,),
using random vector =(
0
,
1
,...,
𝑛−1
) and =
(
0
,
1
,...,
𝑚−1
) to, respectively, express the working state
of the network’s nodes and edges, and using (,),to
express the state of network , then the reliability of the
network ’s Boolean function is
𝑟
,=
1, if is at the state ,,
exists an operational path between
and every node in
0, else.
()
e reliability of a WSN under the multicast model is
𝑁
=
(𝑥,𝑦)∈Ω
Pr
𝑟
,=1,
()
where is the Cartesian product (×), which is the state
space of the network.
2.3. Ordered Binary Decision Diagram. An ordered binary
decision diagram (OBDD) [, ] provides a compact, canon-
ical, and eciently manipulative representation for Boolean
functions.
An OBDD for a nonconstant Boolean function (
1
,
2
,
...,
𝑛
)is a directed acyclic graph. e characteristics of the
OBDDcanbesummarizedasfollows:
() anOBDDhasthreetypesofnodes:root,terminal,and
internal. e root node has no parent or is without
input arcs, the terminal nodes have no child or out
arcs, and the internal nodes have two outgoing arcs;
() the root node of an OBDD represents the function ;
() there are two terminal nodes “” and “,” which
represent constant Boolean functions and ;
() each nonterminal node has four attributes:
𝑢
,var,
low, and high, where
𝑢
is the Boolean function of
the vertex and
𝑢
=(
1
,...,,...,
𝑛
);varis
thevariablelabelingthevertex;lowisthe-node
while var =0, the arc connecting the vertex and
low is -edge, and low =
𝑢
|
𝑢=0
as well as
𝑢
|
𝑢=0
=
(
1
,...,0,...,
𝑛
);highisthe-nodewhilevar=1,
the arc connecting the vertex and high is -edge, and
high =
𝑢
|
𝑢=1
as well as
𝑢
|
𝑢=1
=(
1
,...,1,...,
𝑛
);
then,
𝑢
=
⋅
𝑢
|
𝑢=0
+⋅
𝑢
|
𝑢=1
;
() given the variable ordering :
1
<
2
<⋅⋅⋅<
𝑛
,
variablesinanOBDDareorderedandallthepathsin
the OBDD keep the same variable ordering.
Given a Boolean function and any assignments to its
variables, the function value is determined by tracing a path
from the root to a terminal node following the appropriate
branch from each node. e branch depends on the variable
value of the assignments, and the function value under the
assignments is determined by its path’s terminal node.
For example, Figure shows the binary and the OBDD
for the Boolean function =
1
⋅
2
+
2
⋅
3
,inwhichthe
variable order is :
1
<
2
<
3
. It is obvious that the OBDD
is a directed acyclic graph and stores the same information
more compactly. We trace the path A → B → D → F
andreachtheterminalnode.us,thevalueofthefunction
=
1
⋅
2
+
2
⋅
3
of variable assignment (, , ) is .
3. A Solution Algorithm for the Problem of
WSN Reliability
3.1. Symbolic Formulation of the WSN on the Multicast Model.
WeconvertaWSNonthemulticastmodel,=(,,,),
toasymbolicOBDDformbyencodingtheverticesof
with a length-binary number, where =log
2
num
and
num
was the number of the vertices. Each encoded vertex
of corresponded to a vector of binary variables =
(
0
,...,
𝑛−1
).eedge(V
𝑖
,V
𝑗
)∈of can be represented by
abinaryvector(,)=(
0
,...,
𝑛−1
,
0
,...,
𝑛−1
),where=
(
0
,...,
𝑛−1
)and =(
0
,...,
𝑛−1
)are the binary encodings
of vertex and vertex , respectively. e connecting relation
between two nodes can be represented using the following
characteristic function:
,=
1, ,∈,
0, otherwise.
()
is function implies the relationship between the nodes and
edges of the WSN.
In this study, we assume that the operational probability
of all the nodes was .. en, in do not need to be
剩余14页未读，继续阅读
2010-03-12 上传
2019-07-22 上传
2021-08-08 上传
2024-11-20 上传
2024-11-19 上传
2015-10-28 上传
2019-07-22 上传
weixin_38637884
- 粉丝: 6
- 资源: 869
我的内容管理
展开
最新资源
- Angular程序高效加载与展示海量Excel数据技巧
- Argos客户端开发流程及Vue配置指南
- 基于源码的PHP Webshell审查工具介绍
- Mina任务部署Rpush教程与实践指南
- 密歇根大学主题新标签页壁纸与多功能扩展
- Golang编程入门：基础代码学习教程
- Aplysia吸引子分析MATLAB代码套件解读
- 程序性竞争问题解决实践指南
- lyra: Rust语言实现的特征提取POC功能
- Chrome扩展：NBA全明星新标签壁纸
- 探索通用Lisp用户空间文件系统clufs_0.7
- dheap: Haxe实现的高效D-ary堆算法
- 利用BladeRF实现简易VNA频率响应分析工具
- 深度解析Amazon SQS在C#中的应用实践
- 正义联盟计划管理系统：udemy-heroes-demo-09
- JavaScript语法jsonpointer替代实现介绍
