3053基于网络编码的高效无线传感器网络数据广播算法

___________________收稿日期:基金项目:国家自然科学基金项目(60903019);高等教育学校博士点基金项目(200805321056)无线广播中基于网络编码的隐藏终端解决机制后学知张大方何思茗(湖南大学计算机与通信学院，湖南长沙410082)([e-mail])摘要:无线广播网络中由于没有RTS和CTS机制，因此会产生隐藏终端问题而无法解决。把网络编码的方法应用在无线广播网络中解决隐藏终端，在节点处采用特殊的机制确认碰撞包，再采用网络编码的方法解码碰撞包，从而恢复原始数据包。分析和实验表明网络编码解决机制减少了误码率和丢包率，提高了无线广播网络的吞吐量。关键词:网络编码，无线广播网络，隐藏终端，AhiddenterminalresolutionmechanismbasedonNetworkCodinginWirelessbroadcastNetworksHOUxuezhi,ZHANGdafang,HeSiMing(SchoolofComputerandCommunication,HunanUniversity,Changsha410082,China)Abstract:BecauseofintheabsenceofRTSandCTSmechanisminthewirelessbroadcastingnetwork,thehiddenterminalproblemcannotberesolved.Applicationofthemethodofthenetworkcodinginwirelessbroadcastingnetworktoresolvethehiddenterminalandadoptingaspacialmechanismtoconfirmthecollisionpacketsinthenode.Thenusingthemethodofnetworkcodingtodecodecollisionpacketsandrestoringtheoriginalpackets.Keywords:Networkcoding,Wirelessbroadcastingnetworks,hiddenterminal1引言无线传感器网络已被广泛应用于军事、环境监测、医疗护理、建筑物状态监控等很多方面。在传感器网络中，Sink节点经常需要对所有节点进行广播，比如应用程序开发与调试、代码更新、参数设置、任务分配等。本文所讨论的广播是Sink节点将数据包传输给网络中所有节点的一种操作。该广播必须是可靠、快速并且尽可能地减少能量消耗。网络编码理论[2]融合了编码和路由技术,允许网络中间节点在传统数据转发的基础上参与编码，具有提升网络吞吐量、改善网络负载平衡、提高带宽利用率、节省无线网络节点能量消耗等优点。在无线传感器网络中，无线链路的不可靠性和物理层的广播特性非常适合使用编码的方法。如图1所示，Sink节点广播4个包（p1,p2,p3,p4）到所有节点。各个不同节点接收到的数据包是相互独立的，每个节点都有丢包的情况发生(各链路丢包率为均0.5)。假设每个节点收到了如图1所示的数据包，即节点1收到了p1和p2，丢失了p3和p4，节点2收到了p2和p3，丢失了p1和p4，节点3收到了p3和p4，丢失了p1和p2。在没有网络编码的情况下，Sink节点不得不重传所有的4个包。但是如果利用网络编码，只需要再传送2个编码后的数据包。例如Sink节点可以发送p’1=p1+p2+p3+p4和p’2=p1+2p2+3p3+4p4。尽管每个节点丢失的是不同的数据包，但它们都可以顺利地解码出4个原始的数据包。例如，节点1收到了p1、p2、p’1和p’2，通过高斯消元法就可以解的4个原始包（p1,p2,p3,p4）。在这个例子中，利用网络编码减少了传输的次数，从原来的8次减少到6次。直观的看，发送数据包所消耗的能量与数据包的发送次数在一定程度上是成比例的。减少数据包的传输次数就可以节省能量消耗。若更进一步，在Sink节点发送源数据包的时候就考虑采用网络编码，比如Sink节点最初不是广播4个包（p1,p2,p3,p4），而是先利用网络编码发送6个编码包（因为考虑了丢包的存在，所以发送大于4个的编码包，避免了重传），如p’1和p’2（p’1=p1+p2+p3+p4，p’2=p1+2p2+3p3+4p4）等，同样因为链路的不可靠性会造成节点丢包，但每个节点只要收到其中的任意4个满足系数向量线性独立的编码包，利用高斯消元法就能顺利解码出4个原始包（p1,p2,p3,p4）。使用网络编码后，因为节点收到任意一个已编码的数据包都具有同等概率的作用，从而增强了网络的容错性和鲁棒性。0.50.50.5Sinknode1node2node3P1,p2p2,p3p3,p4图1利用网络编码可减少传输次数本文首次将随机网络编码[3]的思想应用到Sink节点的数据广播中。在Sink节点进行流内网络编码，即对要发送的数据包进行编码后传送，中间节点可进一步对其进行编码。将网络编码与广播特性相结合，通过对接收的多个数据包进行编码信息融合，增加单次传输的信息量，从而减少数据包的传输次数，降低无线传感器网络信息传输过程中的能量消耗，从而节省节点能耗。考虑到在实际应用中，传感器节点失效或传输链路不稳定都导致丢包情况的发生，而使用网络编码后，节点收到同组里的任意一个数据包都是相同的效果，从而增强了网络的鲁棒性。2相关研究本文研究的Sink节点的数据分发是一种将数据包传输给网络中所有节点的一对多的广播方式。与其相关的研究包括两个方面：一个是广播通信，另一个是网络编码。广播通信是无线网络中的一种很普遍的通信方式。洪泛法是简单易行的广播，但盲目洪泛会造成许多信息重复地被传送而产生冗余、竞争以及碰撞，严重时会形成广播风暴。洪泛法会导致巨大的能量开销，直接影响到无线节点电池的寿命，因此如何利用现有的网络资源，减少广播开销，提高能量利用率成为研究的热点之一。用路由的方式实现最小化能量广播是非常困难的，Zagalj等人[4]证明最小化能量广播问题是NP完全问题。概率式洪泛法[5]是节点按照预选确定的概率进行广播。这种广播算法的难度就在于不好控制转发概率值得大小。确定式洪泛法[6]根据邻居节点信息确定给出信息的转发节点，即在保证周围节点最大程度接收信息的前提下，尽量减少转发节点的数量。在网络编码提出后，研究者开始利用网络编码来解决广播通信中的能量有效性问题。Fragouli等[7]首先结合网络编码，针对简单圆形拓扑和网格拓扑的无线全网广播通信提出了一种最小化能量广播方法，并用理论证明了该方法所获得的能量有效性。随后又对随机拓扑的无线网络进行了研究，分析了节点能量传输半径、节点丢包率等因素对最小化能量广播问题的影响。然而他们研究的是网络中每个节点都对其它所有节点广播的多对多广播，不太适合本文中研究的sink节点对所有节点广播的这种一对多的情况。网络编码也被用在单播和组播中。Katti等[8]首次提出一种提高无线网络单播通信吞吐量的网络编码方法COPE，并给出了它的一个具体实现方案。Chachulski[9]等提出了机会路由与流内网络编码相结合的MORE，以增大网络吞吐量为目的。CodeCast[10]利用流内网络编码并以尽可能减少网络延时为目的。Yang等[11]提出了一种无线Mesh网络中一对多的可靠广播算法R-Code，主要针对网络丢包率较高情况下通过建立最小代价生成树来实现的可靠性广播。这些算法利用网络编码所达到的目的各不相同，而本文利用网络编码主要是以减少节点能量消耗为目的。另外这些算法的复杂度和计算代价太高，不适于计算和存储能力有限的无线传感器网络节点。与本文研究最接近的是I-Hong等人提出的用于传感器网络sink节点广播算法AdapCode[12]，其核心思想是节点根据邻居节点的数目确定编码机制，即编码源数据包的个数和发送编码包的个数。Sink节点直接发送若干个源数据包，中间节点都是收到了足够数量的编码包并成功解码成源数据包后，再进行编码，向下一节点转发。与AdapCode不同的是，本文提出的E-Code核心思想是在Sink节点就进行编码，中间节点对已编码包进行再编码后转发。实现编码方式的不同将导致节点的转发机制等问题的处理也会不同，如E-Code是当节点能成功解码包后就不再转发包了，而AdapCode是节点成功解码出源数据包后再进行编码并转发。3基于网络编码的广播算法E-Code3.1基本思想采用流内随机网络编码（intra-flownetworkcoding）的思想，Sink节点将要发送的数据包先进行编码后再发送出去。所有其它节点收到足够的已编码数据包后进行再编码并转发出去，当节点收到足够的编码包后解码出原始的数据包。具体做法是：Sink节点：当Sink节点发送数据时，将所要发送的原始数据分成若干个批次，每批次由m个源数据包组成。这m个数据包记为x1,x2,….xm，并赋予相同的批次标识。假设每个数据包为L比特，当它与要组合的数据包长度不同时，较短的信息附加额外一串“0”。选取m个数，用这m个数作为编码系数，对原始的m个数据包进行线性编码，把原来的m个数据编码成新的n个数据包y1,y2,…yn，记编码第i个数据包时所使用的m个编码系数为g11,g12,…,g1m,，则编码的公式为11111221mnnmnmyxggyxggyx(1)Sink节点在对数据进行编码后，生成y1,y2,…yn个数据包，然后再把这一组数据包的批次标识与每一个数据包的编码向量作为头部信息添加到数据首部，将数据包发出。这种把系数向量随包传送最初来自于Chou[13]的思想。Sink节点的整个编码过程中的数据变化如图2所示。Sink节点发送完同一批次的n个编码包后，停顿T毫秒时间，来确保有足够的活跃节点收到这些编码包。T毫秒过后，Sink节点再进行下一批次数据包的发送。普通传感器节点：m个原始数据包x1x2….xm批次标识g11,g12,g13…,g1my1批次标识g21,g22,g23…,g2my2批次标识gn1,gn2,gn3…,gnmynn个编码后的数据包图2使用网络编码后的数据包如图2所示，节点接收到编码包后，存储编码向量和编码后的结果，以行向量的形式，存储在解码矩阵中。最初，解码矩阵中只包含未经该节点编码的包以及与之对应的编码向量，否则为空。当接收到一个已编码包后，会从中抽取它的编码向量以及编码结果，放入到解码矩阵中。所收到的某一个编码包如果可以增加矩阵的秩，则称之为更新包。每个接收节点收到一个编码包后，首先进行是否是更新包的判断。如果是更新包，则将新数据包存入缓存。当收到n个更新包后，再将这n个更新包进行再编码，随机选取编码系数生成一个新的编码包，以一定的概率p向下一节点广播出去。如果不是更新包，则丢弃该包，也不再继续向下一节点广播。假设节点r进行再编码后的k个数据包为y’1,y’2,…y’k，记节点发送出第i个再编码的数据包时选取的系数为g’i1,g’i2,…,g’in,，则节点r对收到的n个已编码数据包进行再编码可由式(2)表示。节点对它所收到的更新包进行再编码的意义在于通过这样的多次编码可进一步降低编码数据包的线性相关性，增大邻居节点收到更新包的机率。11111221'''''''nkknknyyggyyggyy(2)由式(1)(2)可得出节点r再编码后的数据包(y’1,y’2,…y’k)与源数据包(x1,x2,….xm)的关系如式(3)，新的编码系数向量hij如式(4)，用这组编码系数作为编码后的新系数向量放在已编码数据包的首部。假设11111221'''mkkmkmyxhhyxhhyx(3)111111111111''''mnmkkmkkn