Truthful and Optimal Data Preservation in Base Station-less Sensor Networks: An Integrated Game Theory and Network Flow Approach
Truthful and Optimal Data Preservation in Base Station-less Sensor Networks: An Integrated Game Theory and Network Flow Approach
复制标题
DOI：
10.1145/3606263
复制
发表时间：
2024-01-01
影响因子：
4.1
通讯作者：
Tang，Bin
中科院分区：
文献类型：
--
作者：
Yu，Yuning;Hsu，Shanglin;Tang，Bin
我们的目标是保存大量的数据insidebase-station-less传感器网络（BSNs），同时考虑到传感器节点是自私的。BSN是指部署在具有挑战性和恶劣环境中的新兴传感应用（例如，水下勘探）;因此，在BSN中不存在用于收集数据的数据收集基站。因此，生成的数据必须存储在BSN内部，然后才能上传。我们的目标是通过激励存储和能量受限的传感器节点参与数据保存过程，以最小的能量成本保存BSN内的数据。我们把这个问题称为DPP：BSN中的数据保留问题。以往的研究假设所有的传感器节点是合作的，传感器有无限的电池电量，并设计了一个最小成本的基于流的数据保存解决方案。然而，在分布式环境下，在不同的控制下，资源受限的传感器节点可以表现出自私的行为，只有保存自己的资源，最大化自己的利益。然后，我们建立了一个博弈理论框架，实现可证明的真实和最佳的数据保存BSN。对于一个特殊的情况下，其中节点不受能量约束的DPP，称为DPP-W，我们设计了一个数据保存游戏DPG-1，它集成了算法机制设计（AMD）和一个更有效的最小成本流为基础的数据保存解决方案。我们表明，DPG-1产生传感器节点的主导战略，并提供真实和最佳的数据保存。然而，对于DPP的一般情况（其中节点是能量受限的），DPG-1无法实现真实和最佳的数据保存。利用最小费用流和ILP计算的传感器节点行为的数据包级流观测，我们揭示了DPG-1失败的原因。这是由于操纵AMD技术的自私节点丢弃分组。然后，我们为DPP设计了一个数据保存游戏DPG-2，跟踪和惩罚BSN中的操纵节点。我们表明，DPG-2提供了讲真话的节点占主导地位的战略，并实现了可证明的最佳数据保存与防作弊的保证。通过在不同的网络参数和动态下进行广泛的模拟，我们表明，我们的游戏实现了系统范围内的数据保存解决方案，具有最佳的能源成本，同时强制传感器节点告知其私人成本类型的真相。我们的工作的一个显着特点是它的综合博弈论和网络流的方法。通过观察网络流提供的流级传感器节点行为，我们提出的游戏可以合成“微观”（即，传感器节点的自私和局部）行为并产生目标“宏观”（即，最优和全局）的网络性能。
We aim to preserve a large amount of data generated insidebase station-less sensor networks(BSNs) while considering that sensor nodes are selfish. BSNs refer to emerging sensing applications deployed in challenging and inhospitable environments (e.g., underwater exploration); as such, there do not exist data-collecting base stations in the BSN to collect the data. Consequently, the generated data has to be stored inside the BSN before uploading opportunities become available. Our goal is to preserve the data inside the BSN with minimum energy cost by incentivizing the storage- and energy-constrained sensor nodes to participate in the data preservation process. We refer to the problem as DPP:datapreservationproblem in the BSN. Previous research assumes that all the sensor nodes are cooperative and that sensors have infinite battery power and design a minimum-cost flow-based data preservation solution. However, in a distributed setting and under different control, the resource-constrained sensor nodes could behave selfishly only to conserve their resources and maximize their benefit.In this article, we first solve DPP by designing an integer linear programming (ILP)-based optimal solution without considering selfishness. We then establish a game-theoretical framework that achieves provably truthful and optimal data preservation in BSNs. For a special case of DPP wherein nodes are not energy-constrained, referred to as DPP-W, we design a data preservation game DPG-1 that integrates algorithmic mechanism design (AMD) and a more efficient minimum cost flow-based data preservation solution. We show that DPG-1 yields dominant strategies for sensor nodes and delivers truthful and optimal data preservation. For the general case of DPP (wherein nodes are energy-constrained), however, DPG-1 fails to achieve truthful and optimal data preservation. Utilizing packet-level flow observation of sensor node behaviors computed by minimum cost flow and ILP, we uncover the cause of the failure of the DPG-1. It is due to the packet dropping by the selfish nodes that manipulate the AMD technique. We then design a data preservation game DPG-2 for DPP that traces and punishes manipulative nodes in the BSN. We show that DPG-2 delivers dominant strategies for truth-telling nodes and achieves provably optimal data preservation with cheat-proof guarantees. Via extensive simulations under different network parameters and dynamics, we show that our games achieve system-wide data preservation solutions with optimal energy cost while enforcing truth-telling of sensor nodes about their private cost types. One salient feature of our work is its integrated game theory and network flows approach. With the observation of flow level sensor node behaviors provided by the network flows, our proposed games can synthesize “microscopic” (i.e., selfish and local) behaviors of sensor nodes and yield targeted “macroscopic” (i.e., optimal and global) network performance of data preservation in the BSN.