雷竞技网页版研究与评论-国际期刊雷竞技苹果下载

国际计算机与通信工程创新研究杂志

菜单

在线刊号(2320-9801)印刷刊号(2320-9798)

所有提交的EM系统将被重定向到网上投稿系统．作者被要求将文章直接提交给网上投稿系统各自的日志。

无线传感器网络中一种有效的防止死锁的分组调度方案

J.Nivetha1，A.Deepa2
  1. 印度泰米尔纳德邦金奈市阿波罗工程学院CSE系助理教授
  2. 学生，M.E (CSE)， Ponnaiyah Ramajayam理工学院，Thanjavur，泰米尔纳德邦，印度
有关文章载于Pubmed，谷歌学者

更多相关文章请访问国际计算机与通信工程创新研究杂志

国际计算机与通信工程创新研究杂志

摘要

在无线传感器网络中，对不同类型的数据包进行调度是非常重要的，因为它可以保证不同类型数据包的优先级和公平性，并且延迟最小。在现有的动态多级优先级(DMP)分组调度方案中，传感器节点实际上被组织成一个层次结构。每个节点维护三个级别的优先级队列。我们划分为(i)实时(优先级1)，(ii)从低级别节点接收的非实时远程数据包(优先级2)，(iii)节点本身感知的非实时本地数据包(优先级3)。如果一个实时任务占用资源的时间较长，其他任务需要等待一段未定义的时间，从而导致死锁的发生。这种死锁情况降低了任务调度方案的端到端延迟性能。所提出的方案是对其他死锁预防算法的改进。一个进程请求资源;如果当时资源不可用，它将进入等待状态，可能永远不会执行。本文旨在提出一种资源分配算法，既能保证所请求的资源能够被进程使用，又能降低资源分配决策的开销。

关键字
无线传感器网络，分组调度，实时，非实时，数据等待时间，死锁，资源。

介绍
无线传感器网络(WSN)由于其灵活性、实现成本低、可移动性等优点而获得了极大的价值和重视。传感器网络在未来将发挥越来越重要的作用，特别是在大规模的监测和军事应用中，它由小型和廉价的传感器节点组成，具有有限的内存，有限的计算能力，并使用电池运行。传感器网由一组传感器节点组成，这些节点执行分布式传感和动作任务。传感器能够感知环境信息，行动者能够对环境采取行动。这些节点通过无线和动态通信来监测和控制环境。现有的动态多级优先级(DMP)无线传感器网络报文调度方案，该方案将传感器节点虚拟组织成一个层次结构。到BS节点的跳距相同的节点被认为处于相同的层次结构级别。对于不同级别的节点所感知的数据包，采用时分多址(TDMA)方式进行处理。例如，为最底层的节点分配1号时隙，为最底层的节点分配2号时隙。每个节点维护三个级别的优先级队列。这是因为我们将数据包分类为，如果数据包是实时优先级数据包，则将其放在优先级队列1上。 Non-real-time remote data packet that are received from lower level nodes then the data packets are placed on priority queue 2 and non-real-time local data packets that are sensed at the node itself are placed on priority queue 3. Non-real-time data traffic with the same priority are processed using the shortest job first (SJF)scheduler scheme since it is very efficient in terms of average task waiting time but the a real-time task holds the resources for a longer period of time, other tasks need to wait for an undefined period time, causing the occurrence of a deadlock. This deadlock situation degrades the performance of task scheduling schemes in terms of end -to-end delay. Hence, we would deal with the circular wait and preemptive conditions to prevent deadlock from occurring.
死锁指的是协调和并发问题，其中两个或多个进程无限期地等待共享资源[2]的释放。死锁问题涉及循环等待，其中一个或多个事务正在等待可用资源，而这些资源由其他一些事务持有，这些事务反过来被阻塞，直到第一个事务持有的资源被释放。[7]。死锁进程永远不会终止它们的执行，它们所拥有的资源对任何其他进程都不可用。
死锁是一种不受欢迎的情况;下面列出了死锁的一些后果:
•影响系统吞吐量。
•系统性能下降。
•无论如何，实时应用程序中的死锁都不明显。
•整个或部分系统瘫痪。
•所涉及资源的利用率降为零。
•死锁随着死锁持续时间的增加而增加。
死锁周期不会自行终止，直到正确检测到并解决。
•没有进展
这些都是僵局的后果;让我们来看看在资源分配系统中发生死锁的一些原因:
•系统资源不足。
•不恰当的进程执行顺序。
•不合理的资源分配逻辑[7]
死锁是一种非常不利的情况，在死锁情况下，整个系统或系统的一部分仍然无限期地阻塞，不能终止其任务。因此，开发有效的控制和调度算法来优化系统性能，同时防止死锁的发生是非常重要的。基本上，发生死锁的四个必要条件，即Coffman条件[7]，是:
我。互斥条件:同一资源不能同时被多个进程使用。
2保持等待状态:已经拥有资源的进程可能会请求新的资源。
3非抢占条件:任何资源都不能从持有资源的进程中强制移除，只有通过进程的显式操作才能释放资源。
4循环等待条件:两个或多个进程形成循环链，每个进程等待链中的下一个进程所拥有的资源。
本文提出了一种新的基于阈值的资源分配技术，将资源分配给请求进程。所提出的技术减少了死锁避免所引起的开销，并保证永远不会发生死锁。但是，与死锁检测策略相比，它降低了系统中死锁发生的频率。所提出的基于阈值的技术通过减少死锁避免和恢复过程中产生的开销来提高系统性能。该方法在分配资源时还考虑了进程的到达时间和突发时间。
本文的其余部分组织如下:第二节说明了相关工作，第三节描述了所提出的方法。第四节阐述了我们的仿真结果。最后，本文以第五节作为结语。

2相关的工作
在本节中，我们定义在设计DMP包调度方案时使用的下列术语和因素。

A.Routing协议:
为了提高能源效率和平衡传感器节点之间的能源消耗，我们设想使用基于区域的路由协议。在基于区域的路由协议中，每个区域由一个区域头(ZH)标识，节点遵循一个分层结构，基于它们距离基站(BS)的跳数。例如，距离BS一跳和两跳的区域内的节点分别被认为是level 1和level 2。每个区域还被划分为若干个小正方形，如果正方形S1中存在一个传感器节点，那么它将覆盖所有相邻的正方形。因此，该协议降低了网络中存在任何传感孔[34]的概率，即使节点的相邻方格没有任何传感器节点。

B.TDMA方案:
每个节点级别上的任务或包调度使用具有变长时隙的TDMA方案执行。数据从最底层节点通过中级节点传输到BS。因此，与低级别的节点相比，中级和高级别的节点具有更多的任务和处理需求。考虑到这一点，我们将上层节点的时隙长度设置为更高的值，而下层节点的时隙长度设置为更高的值。另一方面，实时和时间关键的紧急应用程序应该阻止中间节点聚合数据，因为它们应该以尽可能小的延迟交付给最终用户。

C.Fairness:
该指标确保不同优先级的任务在就绪队列中以基于任务优先级的最小等待时间执行。例如，如果任何低优先级任务等待高优先级任务持续到达很长一段时间，公平性定义了一个约束，允许低优先级任务在一定的等待时间后得到处理。

D.Priority:
实时数据和应急数据优先级最高。非实时数据包的优先级是根据感知到的位置和数据的大小分配的。节点x从较低级别节点接收到的数据包优先级高于节点x本身感知到的数据包。但是，如果观察到由于高优先级的非实时远程数据不断到达而导致低优先级的非实时本地数据无法传输，则将其抢占，以便在一定的等待时间后处理低优先级的数据包。然而，这些任务可以被实时紧急任务抢占。如果有两个相同优先级的数据包，大小较小的数据包优先级较高。

E.Motivational例子:
如图2.1所示，在一个传感器节点的多个队列之间调度数据包，在一个节点上被感知的数据包在就绪队列的多个级别之间调度。
在动态多级优先级方案中，在WSN基于zone的拓扑结构中，除了虚拟层次结构的最后一层外，每个节点都有三层优先级队列。实时报文被放在优先级最高的队列中，可以抢占其他队列中的数据包。非实时数据包根据其估计处理时间的某个阈值被放置到另外两个队列中。叶子节点有两个实时和非实时数据包队列，因为它们不接收来自其他节点的数据。

3建议的系统模型
本文讨论了资源分配技术，即将资源分配给请求进程。假设系统有m种资源类型，即R1、R2、R3……Rm，每种类型有α1、α2、α3……αm个实例。进一步，它由n个独立的进程P1,P2,P3…Pn组成，其中，每个进程Pi具有属性(????， ????)，分别为到达时间和最坏情况执行时间。进程根据最小的执行时间(最短作业优先，SJF)分配优先级。为了维护系统中资源分配的状态，需要几个数据结构;它们的定义如下:
我可用:包含m个元素的数组，表示每种资源类型可用的实例数。因此，可用(Rj)是系统中可用的资源类型Rj的数量。
2最大:二维数组n×m，定义每个进程的最大资源需求。如果Max[i][j]等于k，那么进程Pi在其生命周期内最多可以请求k个Rj类型的资源实例。
3分配:二维数组n×m定义了当前分配给每个进程的每种类型的资源数量。如果Allocation[i][j]等于k，那么进程Pi当前被分配k个资源类型为????的实例。
4需要:二维数组n×m表示每个进程剩余的资源需求。如果Need[i][j]等于k，那么进程Pi可能需要k个资源类型Rj的实例来完成它的执行。可以估计为需求[i][j]=最大值[i][j] -分配[i][j]
v。阈值:包含m个元素的数组，表示完成至少一个进程所需的最小剩余资源数。如果阈值[j]等于k，那么至少一个进程Pi将需要最多k个资源类型Rj的实例来完成它的执行。可以估计为Threshold[j]=[need[i][j]∀i=1,2…n]，0]
6要求:一个二维数组n×m，表示进程Pi在执行期间请求的资源数量。如果Request[i][j] = k，则处理Pi请求k个资源类型Rj的实例用于当前执行
7预检验:当事务处于预检查阶段时，只检查队列中的资源可用性并启动事务，不检查所需的资源是否空闲。

A.工作原理
提出了一种基于阈值的技术，在该技术中，系统预留一个阈值数量的资源池，以确保至少有一个进程总是完成并释放它所持有的所有资源。该方法只考虑请求过程的细节和系统数据结构来决定是否授予资源，从而导致等待时间的开销。图3.1所提出的基于阈值的资源分配(TRA)技术体系结构可以说明如下:所提出的方法处理资源分配技术，将资源分配给请求进程。假设系统有m种资源类型，即R1、R2、R3……Rm，每种类型有α1、α2、α3……αm个实例。进一步，它由n个独立的进程P1,P2,P3…Pn组成，其中，每个进程Pi具有属性(????， ????)，分别为到达时间和最坏情况执行时间。进程根据最小的执行时间(最短作业优先，SJF)分配优先级。维护系统中资源分配的状态需要几个数据结构。

四、绩效评估
仿真模型采用C语言编程实现。它用于评估所提出的基于阈值的资源分配的性能，并将其与DMP包调度方案进行比较。从平均数据包等待时间和端到端数据传输延迟两个方面进行比较。

V.CONCLUSION
本文利用基于阈值的资源分配技术，提出了一种有效的无线传感器网络数据包调度方案，以防止循环等待。如果某个实时任务占用资源的时间较长，则其他任务需要等待一段不确定的时间，从而导致死锁。这种死锁情况降低了任务调度方案的端到端延迟性能。因此，我们将处理循环等待和抢占条件以防止死锁的发生，这是一种基于阈值的资源分配技术，通过确保至少有一个进程总是拥有所需数量的资源来避免死锁。仿真结果表明，基于阈值的资源分配技术在平均数据等待时间和端到端延迟方面优于传统方案。

数字一览
图1 图2 图3
图1 图2 图3
图1 图2 图3
图4 图5 图6

参考文献









全球科技峰会