精华内容
下载资源
问答
  • LTE概述

    千次阅读 2019-10-09 17:05:00
    同一系统中,使用OFDMA可以灵活处理多个系统带宽 扁平化结构 当分组调动的功能位于基站时,可以利用快速调度,including 频域调度,以提高小区容量。频域调度可通过OFDMA实现,而CDMA无法实现。 便于...

    LTE概述

    LTE相关组织介绍

    LTE标椎组织

    功能需求 → \rightarrow 标椎制定 → \rightarrow 技术验证
    ngmn → \rightarrow 3GPP → \rightarrow LSTI

    3gpp组织架构

    3GPP网站

    LTE标准进化进展-4G

    冻结时间基本作用功能
    LTE R82009.03定义LTE的基本功能光谱灵活:带宽,双工;新的无线接入:UL:SC-FDMA,UP:OFDMA;多天线技术:发送分集,空间复用;Fast Scheduling;自适应调制编码(AMC);混合自动重传请求(HARQ);自组织网络(SON)
    LTE R92009.12完善家庭基站、管理和安全方面的性能,LTE微微基站和自组织管理功能positioning(定位);SON;EMBMS(改进的多媒体广播组播服务)
    LTE Advance2011.03定义Lte-a的关键技术如relay,载波聚合,8*8MIMO,带宽扩展;协同多点传输(CoMP);Relay(增大网络范围,增强链路性能)

    LTE网络架构

    EPS
    EPC
    E-UTRAN
    MME/S-GW
    e-Node B
    移动性管理实体/服务网关

    EPS:演进分组系统
    EPC:演进分组核心网
    E-UTRAN:只有一种网元eNode B

    LTE全网架构

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Gs3cH5TP-1570611879891)(C:\Users\gxdbi\Desktop\MarkDownd笔记\通信\image\LTE全网架构.png)]

    • 网络结构扁平化

    • 全IP

    • 媒体面控制面分离

    • 与传统网络互通

      EPC网元的功能

    控制面板网元MME(Mobility Management Entity,移动性管理设备),主要用于用户接入控制和移动性管理。
    用户面网元包括S-GW(Serving—Gateway,服务网关),P-GW(PDN—Gateway,PDN—Packet Data Network—网关),用来承载数据业务
    服务数据管理网元HSS(Home Subscriber Server,归属签约用户服务器)EPC的HSS是融合的HLR/HSS,用于存储2G/3G、LTE用户数据、鉴权数据等。
    策略控制网元为PCRF(Policy and Charging Rules Function,策略和计费控制功能),主要用于服务质量(QoS)的策略控制和计费控制。
    PDN GW:P-GW的主要功能包括基于用户的包过滤功能、合法侦听功能、UE的IP地址分配功能、在上/下行链路中进行数据包传输层标记、进行上/下行业务等级计费以及业务级门控、进行基于业务的上/下行速率的控制等。另外,P-GW还提供上/下行链路承载绑定和上行链路绑定校验功能。
    详情请见

    LTE网络架构—Femto网

    n个femto
    Internet
    SeGW
    CN-OSS
    X
    HeMS
    AAA
    HSS
    HeNBGW
    MME
    S-GW

    HeNB(Home evolved Node B,家庭演进基站):Femto无线接入点,完成无线口接入的相关流程。
    SeGW,安全网关,确保非安全传输网络上S1口数据的安全传送
    HeNB GW,Femto网关,完成S1口控制面板/用户面相关流程的代理服务功能
    HeMS:Femto网管系统,提供对HeNB的接入认证、告警、性能等的管理功能
    AAA+HSS:与SeGW相连实现HeNB USIM卡安全认证
    CN-OSS:实现对SeGW、HeNB GW、AAA, HSS等设备管理,与BOSS对接
    控制面

    Femto
    Internet
    SeGW
    X
    HeNB GW
    MME

    User plane:

    femto
    Internet
    SeGW
    x
    HeNB GW
    S-GW

    eNode B基本功能

    具有Node B的全部和RNC1大部分功能:

    • 物理层
    • RLC2 :无线链路控制(Radio Link Control),MAC3, PDCP4
    • RRC功能
    • 资源调度
    • 无线资源管理
    • 无线接入控制
    • 移动性管理

    LTE协议栈

    信令流

    UE
    eNB
    MME

    数据流:

    UE
    eNB
    S-GW

    LTE无线接口—用户平面

    LTE无线接口—控制平面

    无线帧结构----类型1

    • 每个10ms的无线帧被分为10个子帧
    • 每个子帧包含两个时隙,每个时隙0.5ms
    • LTE中,利用NFFT=2048的采样周期定义基本时间单元 T s = 1 15000 ∗ 2048 T_s = {{1}\over{15000*2048}} Ts=1500020481是基本时间单元,所有时域资源都以时间单元 T s T_s Ts表示
    • 任何子帧可上可下

    无线帧结构—类型2

    • 每个10ms的无线帧包括2x5ms,每个半帧由4个数据子帧,1个特殊子帧组成
    • 特殊子帧3个特殊时隙:DwPTS,GP,UpPTS5,总厂为1ms
    • DwPTS和UpPTS长度可配置
    • 支持5ms和10ms上下行切换点
    • 子帧0,5和DwPTS总是用于下行发送

    LTE物理资源分配—天线端口概念

    LTE利用天线端口区分空间上的资源。LTE下行定义了6类天线端口

    • 小区专用参考信号天线端口
    • MBSFN6参考信号天线端口
    • PDSCH7终端专用参考信号天线端口
    • ePDCCH解调用参考信号天线端口
    • 定位用参考信号天线端口
    • CSI参考信号天线端口
      天线端口与物理端口无一一对应大关系

    LTE物理资源分配—子载波

    正交子载波区分频域资源,子载波之间间隔15或7.5kHz

    LTE物理资源分配—RE

    OFDM symbol:每个子载波—I/Q数据
    一个RE----一个OFDM symbol(下行)或者SC-FDMA(上行)—一个天线端口—在BPSK调制承载1bit

    LTE物理资源分配—RB

    $PRB = N_{子载波}\times N_{符号个数} $
    即:时域上连续的 N s y m b D L N_{symb}^{DL} NsymbDL个符号,频域上连续的 N s c R B N_{sc}^{RB} NscRB个子载波 组成,两者由CP类型和子载波间隔决定

    系统占用带宽分析

    • 占用带宽 = 子载波宽度 x 每个RB的子载波数目 x RB数目
    • 子载波宽度 = 15kHz
    • 每RB的子载波数目 = 12

    LTE物理资源分配—REG/CCE/RBG

    REG:(Resource Element Group)为控制区域中RE的集合,映射下行控制信道,并包含4个连续RE
    RBG(Resource block Group):为业务信道资源分配的资源单位,由一组RB构成,分组大小与系统带宽有关
    CCE(Channel Control Element):为PDCCH8资源分配的单位,由9个REG组成

    LTE物理资源分配—控制区域与数据区域

    组成
    常规子帧两个时隙,包括下行 Unicast/MBSFN子帧、下行MBSFN专用载波子帧和上行常规子帧
    特殊子帧三个特殊域组成,DwPTS,GP,UpPTS
    1. 下行 Unicast/MBSFN子帧:控制区域与数据区域进行时分,控制区域OFDM 符号数目可配置
    下行 Unicast/MBSFN 子帧控制区域****OFDM 符号数目
    帧结构类型2中的子帧 1 和子帧 61, 2
    存在****MBSFN 传输的子帧1, 2
    不存在****MBSFN 传输的子帧1, 2, 3
    1. 下行****MBSFN 专用载波子帧中不存在控制区域
    2. 上行常规子帧控制区域与数据区域进行频分

    LTE物理信道概述

    逻辑信道
    传输信道
    无线资源控制RRC
    无线链路控制层RLC
    媒质接入控制MAC
    物理层PHY

    逻辑信道

    MAC向RLC以逻辑信道的形式提供服务。逻辑信道(信息类型):CCH(传输LTE系统所必需的控制和配置信息)与TCH(传输用户数据

    传输信道

    • 对PHY来说MAC以传输信道的形式向PHY提供服务

    LTE物理信号

    下行物理信号包括参考信号和同步信号
    上行物理信号仅有参考信号

    LTE物理信号—小区专用参考信号

    RS干扰:影响信道估计,严重时,将使小区搜索失败或者切换失败。解决方法:规避RS信号在频域上的重叠

    LTE物理信号—MBSFN参考信号

    MBSF参考信号 → \rightarrow MBSF传输的子帧:用于下行MBMS业务的信号估计
    天线端口4

    LTE物理信号—UE专用参考信号

    PDSCH信道估计,支持PDSCH的单天线传输。有高层配置

    LTE物理信号—解调/定位/CSI用参考信号

    作用天线端口
    定位用参考信号(PRS)Z终端定位6
    下行解调用参考信号(DM-RS)EPDCCH信道估计107,108,109,110每个端口对应一个+1和-1的组成序列
    信道状态参考信号(CIS)信道信息CQI,PMI,RI等信息的测量,最大支持8个端口的测量15~22

    LTE物理信号—下行同步信号

    TDD系统,主同步信号(PSS)位于DwPTS的三个符号发送,辅同步信号(SSS)在子帧0/5的最后一个OFDM symbol 发送

    • 主同步信号
      • 一个小区中PSS三选一
      • 3个序列 ← \leftarrow → \rightarrow 物理层小区id组(3个物理层小区id) 一一对应
      • 由Zadoff-Chu序列产生
    • 辅同步信号
      • 两个长度为31的二进制序列交错级联产生
      • 二进制序列由 x 5 + x 3 + 1 x^5 + x^3 + 1 x5+x3+1生成31的M序列循环位移得到
      • 级联序列 + PSS的扰码信号
    • LTE物理层小区ID(PCI) 504 —168 SSS序列 — 3个PCI

    LTE物理信号—上行参考信号

    物理层过程

    • 搜索 PSS**,确定** 5ms 定时、获得小区 ID
    • 解调 SSS**,取得**10ms定时,获得小区ID(PCI)组
    • 计算物理小区标识 N I D c e l l = 3 × N I D ( 1 ) + N I D ( 2 ) N_{ID}^{cell} = 3\times N_{ID}^{(1)} + N_{ID}^{(2)} NIDcell=3×NID(1)+NID(2)
    • 检测下行参考信号,获取BCH的天线配置
    • UE就可以读取PBCH的系统mib消息(PCH配置、RACH配置、邻区列表等)
    • 读取DL-SCH结构基于1.25MHz固定带宽。UE必需的小区信息有:小区总发射带宽、小区ID****、小区天线配置、CP长度配置、BCH带宽

    LTE关键技术

    频域多址技术—OFDM/SC-FDMA

    多址技术要求

    • 更大的带宽
      • 带宽de增加,OFDM信号仍将保持正交,CDMA的性能将受到多径的影响
      • 同一系统中,使用OFDMA可以灵活处理多个系统带宽
    • 扁平化结构
      • 当分组调动的功能位于基站时,可以利用快速调度,including 频域调度,以提高小区容量。频域调度可通过OFDMA实现,而CDMA无法实现。
    • 便于上行功放的实现
      • SC-FDMA相比较OFDMA可以实现更低的峰均比,有利于终端采用更高效率的功放
    • 简化多天线操作
      • OFDMA更容易实现MIMO

    多址方式概述

    • LTE采用OFDM作为下行多址方式
    频域
    时域
    信道编码/交织/加扰
    QAM调制
    串转并
    子载波映射
    IFFT
    加cp
    j
    • 下行SC-OFDMA
    时域
    频域
    时域
    信道编码/交织/加扰
    QAM调制
    DFT
    子载波映射
    IFFT
    加cp
    j

    OFDM基本思想

    • 个子载波之间可以相互交叠
    • 将高速数据流转换成N个并行的低速数据流,并在N个子载波上同时传输。并构成一个OFDM符号

    OFDM—循环前缀

    为什么需要前缀?

    • 个子载波之间需完全正交,完全同步
    • 发射机与接收机精确同频、同步
    • 多径效应引起符号间的干扰
    • 积分区间内周期不完整
      保护间隔和循环前缀:但在多径情况下空闲保护间隔在子载波中造成干扰

    OFDM—主要参数

    • 子载波间隔

      • 15kHZ,用于单播(unicast)和多播(MBSFN)传输
      • 7.5kHz,独立载波的MBSFN传输
    • 子载波数目

      信道带宽MHz1.435101520
      子载波数目721803006009001200
    • 循环前缀长度

      • 一个时隙中不同OFDM符号的循环前缀长度不同

    OFDM—上行SC-FDMA多址方式

    • 利用DFTS-OFDM的特点可以方便的实现SC-OFDMA多址接入
    • 通过改变不同用户的DFT的输出到IDFT的输入的对应关系,输入数据符号的频谱可以被移植不同的位置,从而实现多用户多只输入

    OFDM—DFTS-OFDM关键参数【同OFDM–主要参数】

    • 子载波间隔
      • 15kHZ

    OFDMA VS SC-FDMA

    时域频域
    OFDMA调制完成后,N个符号同时传输较高的峰均比(PAPR):经过IFFT以后,每一个时域上的符号是那N个符号经过相位旋转的和。当N足够大时,每个符号趋于复高斯分布,整体幅度趋于瑞利分布。 → \rightarrow 最大功率与平均功率的比值就会很大。对于OFDM,每个已调的信号映射到不同的子载波上,然后叠加在一起发送,发送的信号是很多时域信号的叠加
    SC-FDMAN个付符号一起调制,一个接一个顺序传输经过DFT和IDFT变换后,接收到的符号周期变短了。每个符号经过DFT扩展到各个子载波上,也就是说每个子载波都有信息承载

    MIMO技术

    多天线技术

    • 上行多天线技术
      • 上行传输天线选择(TSTD)
      • MU-MIMO
    • 下行多天线技术
      • 传输分集:SFBC,sfbc+fstd,闭环Rank1预编码
      • 空间复用:开环空间复用,闭环空间复用以及MU-MIMO
      • 波束赋形
    • 多天线技术分类
      • MIMO
      • SISO
      • SIMO
      • MISO
        LTE的基本配置是DL 2x2 UL 2x1,最大支持4x4

    多天线技术—MIMO对比

    • SU-MIMO:空分复用
      • 两个数据流在一个TTI中传输给UE
    • SU-MIMO:发射分集
      • 只传给UE一个数据流

    SU-MIMO:可通过多链路同时传输,提升路由器与客户端设备之间的网络通信速率,同一时间和同一频段内,路由器只与一个客户端设备进行通讯。客户端设备不能完全占用路由器的无线带宽,那路由器也无法将剩余带宽分配给其它设备使用。

    • MU-MIMO结合SDM
      • 给每个UE传送两个数据流
    • MU-MIMO结合发射分集
      • 给每个UE传送一个数据流

    MU-MIMO:添加了多用户同时通讯机制。可以将全部的无线宽带利用起来。 多用户接入时,各个设备的网络延迟状况都会得到较好的改善。更重要的一点是,MU-MIMO不需要客户端设备提供支持,只要路由器本身支持MU-MIMO技术,那么其在实际使用的过程中就会生效,并通过路由器固件的设置来调整各个无线客户端设备的带宽分配。
    上行支持 MU-MIMO
    目前支持的配置1x2或1x4将来支持2x2或4x4

    多天线技术----UL MU-MIMO

    • 多用户使用相同的时频资源
    • 需要不同用户间相互协作完成
    • 有效提升上行吞吐量
    • 主要用于小区中心区域用户
      UL MU-MIMO技术使得上行小区的吞吐量提升了70-80%

    多天线技术----波束赋形

    • 基于码本的波束赋形
      • 终端 → \rightarrow 选择系统推荐的PMIKaTeX parse error: Undefined control sequence: \rightaeeow at position 1: \̲r̲i̲g̲h̲t̲a̲e̲e̲o̲w̲基站
      • 需要使用小区参考信号 ,不需要终端参考信号
    • 非码本的波束赋形
      • 利用上下行信道的互易性。利用上行信道矩阵估计下行信道矩 H D L = H U L T H_{DL} = H_{UL}^T HDL=HULT
      • 利用上行信道的测量值估计下行发射的参数
      • 基站计算天线阵子的权值,控制各个阵子发送信号的幅度和相位,使信号同相叠加
      • 使用小区参考信号(CRS)和终端参考信号
    • 双流波束赋形

    多天线技术—增强型MIMO技术

    • 最大下行支持8天线,最大支持8层传输,即8x8 MIMO
      • 提高下行吞吐量和频谱效率
      • 基于CSI-RS进行闭环TM9码本测量
      • TDD支持开环TM9多流业务发射
    • 上行最大4x4
      • 大幅提高吞吐量和频谱效率
      • PUCCH(物理上行控制链路)支持基于SORTD9的发射分集,提高上行控制信息的传输质量
      • SRS10支持多端口发射,配合PUSCH进行空间服用的码本测量
      • TDD模式可用于TM9开环SU-MIMO增强
    • MU-MIMO进一步增强,如SU-MU的动态切换、UE专用导频的引入等,用来提高MU-MIMO的性能

    多天线技术----CoMP(Coordinated Mulitple Point,协同多点传输)

    • 不管是同构小区基站单元,还是异构网中RRH,RRU,LPN等射频单元
    • 改善小区边缘用户服务质量,提高小区的吞吐量

    多天线技术 ---- DL CoMP

    • 联合处理JP(Joint Processing)
      • 同一时频资源协作集中多节点可获得数据,各个节点联合进行数据处理,包括JT,DPS
        JT(Joint Transmission)一个UE数据同时多个点进行传播,改善信号质量,或消除其他UE的干扰
        DPS(Dynamic point selection)一个时刻,CoMP协作点集中只有一个点传输UE数据
    • 协同调度(CS)\协同波束赋形(CB)
      • 数据仅仅在服务小区可获得,并由服务小区进行数据的传输,但是用户的调度和波叔的确定由协作集中的多个小区共同确定。

        CS(Coordinated Scheduling)通过调度使其他协作节点避免与目标小区相同的资源上调度用户,或者让协作节点在相同资源上以低功率发送
        CB(Coordinated Beamforming)通过协作的方式使邻小区选择恰当的BF权值来抑制邻小区对该UE的干扰

    多天线技术----UL CoMP

    • 联合接受JR(Joint Reception)
      • UE上行发数据同时由多个协作小区接收,通过小区间信息的交互,最终得到UE的解调性能。可分为:

        JE(Joint Equalization)将CoMP协作集中的所有天线和流统一进行均衡处理,相对而言复杂度更高
        SC(Soft Combing)每个小区解析出的邻小区用户数据传递到邻小区,用于信息的软合并

    高阶调制技术

    HARQ技术

    混合自动重传请求(HARQ)

    • 前向纠错码FEC
    • 自动重传请求arq
    • HARQ = FEC + ARQ

    FEC通信系统

    优势劣势
    高:系统传输效率;自动错误纠正,无反馈及重传;低延时可靠性低;对信道自适应能力低;为保证较高的可靠性,编码时间长,编码效率低,复杂度和成本高

    ARQ通信新系统

    优势劣势
    低复杂;高可靠;适应性强连续性,实时性,传输效率低

    HARQ机制

    以FEC进行传输,ARQ进行反馈

    HARQ—定时关系

    • ACK/NACK定时:对于子帧n中的数据传输,其ACK/NACK在n+k子帧中进行传输,对于FDD,k = 4;TDD, k > 3
    • 重传与初传之间的定时关系:同步、异步HARQ协议
    • LTE上行为同步HARQ协议:如果重传在预先定义好的时间进行,接收机不需要显示告知进程号。
      • 由PHICH11传输子帧的位置 → \rightarrow PUSCH传输子帧的位置
      • 与PDCCH → \rightarrow PUSCH的定时关系相同
    • LTE下行异步:如果重传在上一次传输之后的任何一段时间上进行,接收机需要显示告知具体进程号。

    HARQ—自适应、非自适应HARQ

    • 自适应:可以改变初传的一部分或者全部的属性,例如调制方式,资源分配等,这些属性的改变需要信令的额外通知。
    • 非自适应:重传时改变的属性是发射机与接收机协商好的,不需要额外的信令通知

    LTE下行:自适应:PDCCH实现,不反馈NACK信令
    LTE上行:非自适应:由PHICH信道中承载的NACK触发

    RTT(Round Trip Time,回环时间)与进程数

    RTT的大小:传输延时,接收时间,处理时间。TDD系统的时隙比例,传输所在子帧的位置有关

    链路自适应技术—AMC

    实现方式:功率控制和速率控制
    一般情况下是指:速率控制,LTE中为自适应编码调制技术(Adaptive Madolation and Coding,AMC) → \rightarrow eNode B根据UE反馈的信道状况调整不同的调制方式
    对于长时延的分组数据,Amc提高系统容量的同时不增加对邻区的干扰

    快速MAC调制技术

    小区干扰消除

    TD-LTE VS LTE-FDD



    1. 基站控制器,负责管理基站,实施通信控制 ↩︎

    2. 无线链路控制(Radio Link Control,RLC)协议的主要目的是将数据交付给对端的RLC实体。所以RLC提出了三种模式:透明模式(Transparent Mode,TM)、非确认模式(Unacknowledged Mode,UM)和确认模式(Acknowledged Mode,AM) ↩︎

    3. E-UTRA提供了两种MAC实体,一种是位于UE的MAC实体,一种是位于E-UTRAN的MAC实体。UE的MAC实体与E-UTRAN的MAC实体执行不同的功能,图33从UE的角度给出一种MAC实体结构。[https://baike.baidu.com/item/LTE%20MAC%E5%B1%82/16844150?fr=aladdin](https://baike.baidu.com/item/LTE MAC层/16844150?fr=aladdin) ↩︎

    4. PDCP*(Packet Data Convergence Protocol)分组数据汇聚协议PDCP是对分组数据汇聚协议的一个简称LTE系统PDCP协议层的主要目的是发送或接收对等PDCP实体的分组数据。该子层主要完成以下几方面的功能:IP包头压缩与解压缩、数据与信令的加密,以及信令的完整性保护。 ↩︎

    5. DwPTS是下行导频时隙,共96个chips,TD-SCDMA的帧结构是一个帧被分成了7+3个时隙,7个常规时隙,还有一个DwPTS(下行导频时隙),一个UpPTS(上行导频时隙,共160个chips),GP(保护间隔,96个chips),GP位于DwPTS和UpPTS之间 ↩︎

    6. MBSFN,是Multicast Broadcast Single Frequency Network的缩写,意思是多播/组播单频网络。它要求同时传输来自多个小区的完全相同的波形。这样一来,UE接收机就能将多个MBSFN小区视为一个大的小区 [1] 。此外,UE不仅不会受到相邻小区传输的小区间干扰,而且将受益于来自多个MBSFN小区的信号的叠加。不仅如此,诸如G-RAKE等先进的UE接收机技术还能解决多径传播的时间差问题,从而消除小区内干扰。 ↩︎

    7. Physical Downlink Shared Channel – 物理下行共享信道FACH或DCH相伴而存在,因此作为传输信道载体的PDSCH也不能独立存在。DSCH数据可以在物理层进行编码组合,因而PDSCH上可以存在TFCI,但一般不使用SS和TPC,对UE的功率控制定时提前量调整等信息都放在与之相伴的PDCH信道上。 ↩︎

    8. PDCCH (Physical Downlink Control Channel) ↩︎

    9. SORTD:空间正交资源传输分集。基本思想是在不同的天线端口上使用不同的正交资源(即不同的PUCCH资源,RB、cyclic shift或orthogonal sequence不同)来传输同一UE的同一上行控制信息(UCI)。却减少了上行容量 ↩︎

    10. SRS:Sounding Reference Signal(上行探测参考信号)作用:上行信道估计,选择MCS和上行频率选择性调度,TDD系统中,估计上行信道矩阵H,用于下行波束赋形。 ↩︎

    11. PHICH全称为Physical hybrid ARQ indicator channel,即物理HARQ指示信道。 ↩︎

    展开全文
  • 无线传感器网络复习大纲

    千次阅读 多人点赞 2019-04-30 10:31:40
    串扰(共享信道中每个节点都能接收到数据,但不都是有用的,这会造成浪费)  3、3 WSN MAC协议分类:  按节点接入方式分类:  侦听MAC协议:采用间断侦听的方式  唤醒MAC协议:采用基于低功耗的...

    第一章

    考点:

    无线传感器网络组成部分,概念、特点(了解)

           分布式特点(了解)

           实时性、时效性(了解)

           常见拓扑结构(了解)

           WSN几个分层、分层的功能(了解)

           自组织网络多跳传输特点(了解)

     

    1、1无线传感器网络介绍

    无线传感器概念:无线传感器网络是一种特殊的无线通信网络,它是由许多个传感器节点通过无线自组织的方式构成的,应用在一些人们力不能及的领域。能够实时地监测、感知和采集节点部署区的环境或观察者感兴趣的感知对象的各种信息,并对这些信息进行处理后以无线的方式发送出去。

     

    无线传感器组成:多个无线传感器节点和少数几个汇聚节点、外部网络构成

     

    无线自组网:自组织:在节点位置确定之后,节点需要自己寻找其邻居节点,实现相邻节点之间的通信,通过多跳传输的方式搭建整个网络,使网络能够稳定正常的运行。

     

    WSN和无线自组织网络(Ad hoc)共有的特点:

           ①、自组织:在节点位置确定之后,节点能够自己寻找其邻居节点,实现相邻节点之间的通信,通过多跳传输的方式搭建整个网络,并且能够根据节点的加入和退出来重新组织网络,使网络能够稳定正常地运行。

           ②、分布式:网络的感知能力由若干冗余节点共同完成,每一个节点具有相等的硬件资源和通信距离,没有哪一个节点严格地控制网络的运行,节点消亡之后网络能够重组,任意一个节点的加入或退出,都不会影响网络的运行,抗击毁能力强。

           ③、节点平等:除了SINK节点以外,无线传感器节点的分布都是随机的,在网络中以自己为中心,只负责自己通信范围内的数据交换;每个节点都是平等的,没有先后优先级之间的差别,每个节点既可以发送数据也可以接收数据,具有相同的数据处理能力和通信范围。

           ④、安全性差:对于自组织网络来说,每一个节点的通信范围是非常有限的,因此它只能跟自己通信范围内的节点进行通信,采用的无线信道,非相邻节点之间的通信需要通过多跳路由的形式来进行,因此数据的可靠性没有点对点高。

          

     

     

    WSN独有的特征:(最基本的特点:节点的可感知、微型化、自组织能力)

    ①、计算能力不高:无线传感器节点分布非常密集,大量节点决定了每个节点的成本不高,在限定的成本下采用的处理器处理速度就比较低,只能处理相对简单的数据,并且节点的队列缓存存储长度也非常有限,不适用于特别复杂的计算和存储,在传感器网络就要考虑节点的拥塞控制。

    ②、能量供应不可替代:无线传感器节点电池不可替代,每一个节点有自己的生命周期,因此,在能量节省与信息处理之间找到平衡点能够最大限度地节省能量

    ③、节点变化性强:网络的自组织和分布式等特点决定了网络必须能够快速重新构造网络,能够动态适应网络变化。

    ④、大规模:为了保证数据的可靠、高效传输,无线传感器网络通过采用大量的具有相同硬件设施的节点来采集数据,有许多节点设置采集的数据都是一样的,因此这样就能够实现数据的冗余,保证数据最终能传输到目的节点。

    ⑤、节点资源有限:如节点的电源能量、通信能力、计算存储能力有限。而且难以维护,对节点运行的程序包括使用的存储空间、算法时间开销有较高的要求。

    ⑥、时效性:无线传感器网络采集的信息需要在一定时间内及时送达观察者或是数据处理中心,对可能发生的事故和危险情况进行及时预告和提醒。

     

     

           无线传感器网络的系统结构———节点结构

     

     

     

     

    无线传感器网络的系统结构———网络拓扑结构

     

           ①、平面网络结构:无线传感器网络中最简单的一种拓扑结构,所有节点为对等结构,具有完全一致的功能特性

    分及网络结构:分级网络结构分为上层和下层两个部分:上层为中心骨干节点;下层为一般传感器节点。这种网络拓扑结构扩展性好,便于集中管理,可以降低系统建设成本,提高网络覆盖率和可靠性

     

     

     

     

    Mesh网络结构:Mesh网络结构是一种新型的无线传感器网络结构,该结构是规则分布的网络结构,该结构中通常只允许节点和节点最近的邻居通信

     

     

    无线传感器网络的系统结构———协议结构

           ①、物理层:负责载波频率产生、信号的调制解调等工作,提供简单但健壮的信号调制和无线收发技术。

           ②、数据链路层:差错控制:媒体访问控制;主要负责网络结构的建立和为传感器节点有效合理的分配资源。差错控制;保证源节点发出的信息可以完整、无误地到达目标节点。

           ③、网络层:负责路由发现和维护,是无线传感器网络地重要因素。无线传感器网络中,大多数节点无法直接与网关通信,需要通过中间件进行多跳路由。(以数据为中心)

    ④、传输层:负责将传感器网络的数据提供给外部网络,也就是负责网络中节点间和节点与外部网络之间的通信。

    ⑤、应用层:主要由一系列应用软件构成,主要负责监测任务。这一层主要解决三个问题:传感器管理协议、任务分配和数据广播管理协议,以及传感器查询和数据传播管理协议。

     

     

    无线传感器网络各平台管理功能:

    能量管理平台:管理传感器节点如何使用资源,在各个协议层都需要考虑节省能量

    移动管理平台:检测传感器节点的移动,维护到汇聚节点的路由,是的传感器节点能够动态跟踪其邻居的位置。

    任务管理平台:在一个给定的区域内平衡和调度检测任务。

     

     

     

     

    第二章、无线传感器网络物理层设计

     

     

    考点:

    物理层的功能、协议、介质、特点(了解)

    无线电波使用频段限制以及原因(了解)

    传输调制、特点(了解)

     

    2、1无线传感器网络物理层概述

           物理层:位于最底层,向下直接与物理传输介质相连接,主要负责数据的调制、发送与接收,是决定WSN的节点体积、成本以及能耗的关键环节。

     

           主要功能:为数据终端设备提供传送数据的通路;传输数据;其他管理工作,如信道状态评估、能量检测等。

     

           传输介质:主要包括无线电波、红外线和光波。

     

           物理层特点:物理层研究集中在传输介质、频率选择、调制机制三个方面;在设计中需要考虑成本和功耗、通信速率、通信频段、编码调制方式的选择、物理帧结构的问题

     

    2、2频谱分配:

                  频率选择:

                  频率的选择影响无线传感器网络性能、体积、成本(当前频段的选择大都集中在433-464MHz、902-928MHz以及2.4-2.5GHz ISM频段)

                         ①、从节点功耗的角度考虑自身能耗、传输损耗与工作频率的关系。在传输同样的有效距离时,载波频率越高则消耗能量越多,因为载波频率越高对频率合成器的要求也就越高。射频前端收发机中频率合成器可以说是其主要的工号模块,波长越短传播损耗越大。

                         ②、从节点的物理层集成化程度、成本的角度来考虑,虽然当前的CMOS工艺已经成为主流,但是对大电感的集成化还是一个非常大的挑战,由于无线传感器网络是一种面向应用的网络,FCC组织给出2.4GHz的一个全球ISM频段。

     

    2、3 WSN物理层调制解调技术:

           传统的无线通信系统需要解决的问题:频谱效率、误码率、环境适应性,以及难以实现的难度和成本。

           WSN需要解决:节能和成本

     

           常用调制方式:

                  模拟调制、数字调制、扩频通信、UWB通信技术

           B-ary数字调制(二进制数字调制):

                  应用于启动时间较短、能量消耗大的的系统

           M-ary数字调制(多进制数字调制)

                  应用于WSN,启动能量消耗低的系统

          

           B-ary和M-ary的比较:M-ary传输的信息量是B-ary的log2M倍,节省了传输时间,但是实现复杂且抗干扰能力不如B-ary,M越大误码率越大,M-ary电路更加复杂,能耗大。

     

     

    第三章 无线传感器网络数据链路层设计

     

    考点:

    区分WSN的MAC协议(了解)

    WSN数据链路层协议模型(二维、跨层)(掌握)

    基于竞争的MAC协议题、图(掌握)

     

           3、1 无线传感网络数据链路层概述

                  数据链路层:就是利用物理层提供的数据传输功能,将物理层的物理连接链路转换成逻辑连接链路,从而形成一条没有差错的链路,保证链路的可靠性。数据链路层也向它的上层——网路层提供透明的数据传输服务,主要负责数据流多路复用、数据帧监测、媒体介入和差错控制,保证无线传感器网络内点到点以及多点到多点的连接。无线传感网络的数据链路层研究的主要内容就是MAC差错控制。怎样实现无线传感器网络中无线信道的共享,即介质控制协议(MAC)的实现是WSN中数据链路层研究的一个重点,MAC协议的好坏直接影响到网络的性能优劣。

     

     

           3、2 WSN数据链路层关键问题

                  ①、网络性能的优化:在MAC协议中,WSN的关键性能指标不是独立存在的,而是互相影响的,在提高一种性能的同时可能会降低其他性能。现在所提出的MAC协议往往只考虑一种或两种性能指标,没有综合各种指标使之达到更好的性能;

                  ②、跨层优化:WSN区别于传统无线网络最重要的是WSN各层之间能够实现合作与信息共享。在WSN中采用了跨层设计,各层之间能够通过共享一些信息来共同调节网络的性能。

                  ③、能效问题:WSN节点中,能量消耗主要用于无线信号的收发;无线通信模块一般有四个状态:发送、接收、空闲、休眠,四个状态能量消耗逐级递减,协议必须合理选择节点侦听和休眠的时间比例;还需考虑休眠期间节点的接收问题和缓刑期间节点收发的最大利用率问题,以最大限度地节省能量。

                         MAC的多余能量开耗主要体现在以下几个方面:

    碰撞:无线信道上两个节点同时发送数据,这将发射失败,造成大量的能量浪费。

    持续监听:在无线传感器网络中的接受节点无法预测数据何时到达,另外每个节点还需要侦听各节点的拥塞状况,因此节点必须始终保持监听状态,以防特殊情况的发生,这会浪费很多能量。

    控制开销:为了保证WSN的可靠性,MAC层协议需要使用一些控制分组来调节节点状态,但这些控制分组中不存在有用的数据,因此也会消耗一部分能量。

                  ④、公平性:每个节点都有相同的权利来访问信道,每个节点能量消耗保持大概的平衡,延长网络寿命。

                  ⑤、可扩展性:WSN与其他无线网络相比,具有规模大、分布密集等特点。网络的节点分布结构会动态性地变化,因此必须要有可扩展性。

                  ⑥、信道共享问题:多跳共享、信道复用方式。

                         两个问题:数据冲突(碰撞);串扰(在共享信道中每个节点都能接收到数据,但不都是有用的,这会造成浪费)

           3、3 WSN MAC协议分类:

                  按节点接入方式分类:

                         侦听MAC协议:采用间断侦听的方式

           唤醒MAC协议:采用基于低功耗的唤醒接收机来实现,当然也有集合侦听和唤醒两种方式的MAC协议,如低功耗前导载波侦听MAC协议。

    调度MAC协议:使用于广播中,广播的数据信息包含了接收节点何时接入信道与何时控制接收节点开启接收模块。

                  按信道占用数划分:单信道(主要)、双信道、多信道

                  按分配信道方式划分:竞争MAC协议随机接入

     

     

           3、4 WSN的MAC协议:竞争型、分配型、混合型、跨层MAC协议

     

           基于竞争MAC协议:根据WSN负载量小、针对节点间的公平性以及通信延时要求不高等特点来设计的,其主要的设计目标是提供大规模分布式网络所需的可扩展性。并同时降低能耗。

                  ①、S-MAC协议:

    把时间分为多个时隙,每个时隙中又划分为侦听、睡眠两个状态

                  周期性侦听和睡眠

                  冲突避免

                  自适应侦听

                  分片传递消息,每个子段都会返回ACK应答

          

                  ②、T-MAC协议:

                  相对于S-MAC协议来说,保持了S-MAC的周期,根据网络负载的流量自适应地调整激活的时间。

     

    T-MAC协议规定,当邻居节点还没有结束通信时,节点不能进入到睡眠状态,因为该节点很有可能就是下一个数据的目的节点。假设节点检测到串扰以后能够触发一个空闲间隔TA,TA必须要足够大,以保证节点能够监测到串扰的CTS

     

     

    未来请求发送:采用提前通知需要接收数据的节点的方法来实现早睡的避免:

    如上页中的a所示,当节点C接收到CTS后,除了触发自己保持监听状态之外,还发送一个FRTS分组给节点D,FRTS分组中含有节点D需要等待的时间,在此空闲状态中,节点D必须要保持侦听状态。

    在节点C发送FRTS时看哪个节点会干扰节点A发送的数据,因此节点A需要延迟原数据的发送响应的时间,但是又必须保持对信道的占用,因此节点A在这段时间内发送一个与FRTS一样长度的分组,该分组不包含任何有用的数据,然后才接着发送有用数据信息。从而数据传到节点C之后节点D还是处于唤醒状态,保证数据的实时传输。

    由于采用了未来请求发送机制,协议需要增加一个FRTS分组传输的时间,该方法提高了系统吞吐量和实时性,但是多了一些控制消息,相应地要消耗能量。

     

     

    满缓冲区优先:当节点的缓冲区快满时,节点对收到的RTS分组不回复CTS,而是立即向缓冲区内数据的接收节点发送RTS,建立连接之后发送数据,以减轻缓冲区负载。如前页中的b所示,节点B向节点C发送RTS,而节点C因为缓冲区满不回复一个CTS分组,而是向节点D发送RTS以求数据传输。

     

    ③、Sift协议

    对CSMA/CA机制进行修改,竞争窗口的大小是原本就设定好的,采用非均匀概率来决定是否发送数据,它具有以下几个特点:

    WSN基于空间的竞争

    基于事件的报告方式

    感知事件的节点密度的自适应调整

     

     

     

    基于分配的MAC协议

           ①、SMACS:

    关键技术:节点在上电后先进行邻居发现,每发现一个邻居,这一对节点就形成一个双向信道,即一个通信链路。在两个节点的超帧中为该链路分配一对时隙用于双向通信。随着邻居的增加,超帧慢慢地被填满。每对时隙都会选择一个随机的频点,减少邻近链路冲突的可能。这样全网很快就能在初始化建立链路,这种不同步的时隙分配称为异步分配通信

     

                  移动性管理-EAR算法

     

    EAR算法定义了一种新的信令机制,主要使用4种消息,建立移动节点和静止节点之间通信链路的机制主要有以下步骤:

     

    (1)静止节点会每间隔固定个超帧发送一次BI消息,移动节点在接收到静止节点的BI消息后将开始连接过程。

     

    (2)静止节点在接收到MI消息后需要检查连接是否可以建立。

     

    (3)连接建立后,移动节点在移动过程中会接收到新的邻近静止节点发送的BI消息,移动节点会根据信道质量选择淘汰邻居节点记录中连接质量较差的邻居节点。

     

     

    ②、TRAMA:

    TRAMA协议将一个物理信道分成多个时隙,通过对这些时隙的复用为数据和控制信息提供信道。每个时间帧分为随机接入和分配接入两部分

    为了提高能量效率,TRAMA尽可能地让节点处于睡眠状态,通过重用已经分配但未使用的时隙来提高带宽利用率。在分配接入周期任一给定的时隙t中,任一节点的状态是由该节点的两跳邻居信息和该节点的一跳邻居发布的分配信息来确定的,有发送、接收、睡眠三种中的一个状态。

     

     

    混合型MAC:

    ①、ZMAC:

    ZMAC协议是一种混合型MAC协议,采用CSMA机制作为基本方法,在竞争加剧时使用TDMA机制来解决信道冲突问题。

    在网络部署阶段,节点启动以后ZMAC协议将顺序执行以下步骤:邻居发现→时隙分配→本地时间帧交换→全局时间同步。在网络的运行过程中,除非网络拓扑结构发生重大变化,否则节点不会重复上述步骤,避免浪费能量。

     

     

    跨层MAC:

    MINA:

    MINA是一种基于跨层设计的大规模无线网络协议架构,网络通常由数百个低电量低运算能力的传感器节点组成,同时网络中还有一些基站节点,基站通常具有较强的运算能力,并具有充足的能量。

     

    在MINA架构中,节点分为三种类型:

    大量静止的低容量(内存、CPU、能量)传感器节点;

    少量手持移动节点;

    静止的大容量基站节点。

     

     

     

    根据距离基站的跳数,每个节点的邻居也可以分为三类,即内部邻居、同等邻居、外部邻居。距离基站跳数比本地更小的邻居为内部邻居,跳数相同的邻居为同等邻居,跳数更大的邻居为外部邻居。

     

     

     

    第四章 无线传感器网络的网络层

     

    考点:

           什么是路由、路由维护、选择?(了解)

           区分WSN网络层路由协议(了解)

     

     

    一、无线传感器网络网络层概述

           路由:路由是指分组从原到目的地时,决定端对端路径的网络范围的进程

           WSN网络层概述:在WSN中,路由协议主要用于确定网络中的路由,实现节点间的通信。但是由于受节点能量和最大通信范围的限制,两个节点之间往往不能直接进行数据交换,而需要以多跳的形式进行数据的传输。无线传感器的网络层就主要负责多条路由的发现和维护,这一层的协议主要包括以下两个方面:

           路由的选择:即寻找一条从源节点到目的节点的最优路径;

           路由的维护:保证数据能够沿着这条最优路径进行数据的转发。

     

           WSN网络层与传统网络的区别特征:

                  大规模分布式应用

                  以数据为中心

                  基于局部拓扑信息

                  基于应用

                  数据的融合

          

           WSN网络层发展:

                  最优路径选择

                  安全性

                  QoS保证

                  能量高效利用和均衡

          

           WSN路由协议特点:

                  电池不可替换,高效、均衡利用能量

                  协议应精简,无复杂算法,无大容量冗余数据需要存储,控制开销少

                  网络互连通过SINK节点来完成,其余节点不提供网外通信

                  网络无中心节点,多基于数据或位置的路由算法机制

                  由于节点的移动或失效,一般采用多路径备选

     

           挑战:

                  节能、高扩展性、容错性、数据融合技术、通信量分布不均匀

          

          

    二、无线传感器网络网络层分类

           根据节点在路由过程中是否有层次结构,作用是否有差异,可以分为平面路由协议和层次路由协议

           根据路由建立时机与数据发送的关系,可分为主动路由协议、按需路由协议和混合路由协议。

           根据传输过程中采用路径的多少,可分为单路径路由协议和多路径路由协议

           根据节点是否编址、是否以地址表示目的地,可分为基于地址的路由协议和非基于地址的路由协议

           根据数据在传输过程中是否进行数据融合处理,可分为数据融合的路由协议和非数据融合的路由协议

           根据是否以地理位置来表示目的地、路由计算中是否利用地理位置信息,可分为基于位置的路由协议和非基于位置的路由协议

           根据是否以节点的可用能量或传输路径上的能量需求作为选择路由的根据,可分为能量感知路由协议和非能量感知路由协议

           根据路由建立是否与查询相关,可分为查询驱动路由协议和非查询驱动路由协议

     

    三、无线传感器网络层路由协议

           较为常用的路由协议有:基于数据的路由协议、基于集群结构的路由协议、基于地理位置的路由协议。

          

           基于数据的路由协议

           ①、SPIN协议:

                  概述:SPIN协议是一类基于协商,以数据为中心的路由协议。该协议假设所有的网络节点都是潜在的SINK节点,某一个要发送数据的节点把数据传送给任何需要该数据的节点,并通过协商机制减少网络中数据传输的数据量。节点只广播其他节点没有的数据以减少冗余数据,从而有效地减少能量消耗。(ADV:广播数据包;REQ:请求包;DATA:数据包)

                   

                  当接受到ADV报文的节点发现已经拥有了ADV报文中描述的数据,那么它不发送REQ报文,能量较低的节点也不发送REQ报文(SPIN2)

                  该协议解决的关键问题:Flooding协议(所有节点转发数据)、Gossiping协议(随机节点转发数据)的内爆和重叠问题。

                         内爆:节点向邻居节点转发数据包,不管其是否收到过相同数据;

                         重叠:感知节点感知区域有重叠,导致数据冗余。节点多次受到来自同一区域的节点的同一事件的数据。

     

                  该协议的优点:

    通过节点间的协商解决内爆和重叠问题;

                         在路由选择中使用了能量阈值,可以提高网络生存时间

                         不需要路由维护(没有路由表)

                         对数据进行融合

                         对网络拓扑结构变化不敏感,可用于移动WSN

     

                  该协议的缺点:

                         本质上还是SPIN向全网扩散新信息,开销较大

                        

           ②、DD协议:

                  DD(定向扩散协议):是一种以数据为中心的路由协议,采用的是基于查询的方法。通过汇聚节点在全网广播自己需要的数据,同时在广播的过程中形成了一条由节点到汇聚节点的路径,节点采集到数据后会沿着这条路径来传送数据,汇聚节点通过选择一条最优的路径来接收数据。

                  DD协议基本思想:

                         三个不同的阶段:

    兴趣扩散(汇聚节点向全网广播一条被称为兴趣的数据包,告知自己需要的数据)

                                梯度建立:兴趣的数据包被中间节点逐步转发到网络中相关节点,逐步转发建立多条从兴趣的源节点到汇聚节点

                                路径加强:当网络中的相关节点采集到兴趣数据包中所要求的节点之后,采取的也是广播的方式来向汇聚节点发送数据,通过多跳方式最终传送到汇聚节点,汇聚节点就会从多条路径接收到源节点传过来的数据,之后,Sink节点根据最小代价原则从这些路径中选择一条最优的路径来继续接收数据,其余路径将被放弃。

     

                  DD协议优点:

                         数据中心路由,定义不同任务类型/目标区域消息

                         路径加强机制可显著提高数据传输的速率;

                         周期性路由:能量的均衡消耗

     

                  DD协议的缺点:

                         周期性的泛洪机制——能量和时间开销都比较大;

                         节点需要维护一个兴趣消息列表,代价较大;

     

    ②、集群路由协议

    集群结构路由协议是一种分层的路由协议,网络被划分成多个簇,每个簇都有一个簇头和许多个簇成员组成。每个簇成员如需跟其余簇的成员通信首先与簇头通信,通过簇头来与其余簇进行通信;簇头节点的职责就是管理好本簇内节点,完成本簇分布范围内数据的搜集,并负责簇间的通信;在网络规模比较大的情况下,簇头又可以再次分簇,从而形成一个多层网络;分层路由扩展性非常好,对于大规模的无线传感器应用具有很高的使用价值;

     

           LEACH协议:

                  每个节点直接与SINK节点通信:

                         节点能量消耗过大;节点密度较大时冲突过大,效率低

                  LEACH算法:

                         簇头节点作为一定区域所有节点的代理,负责和Sink的通信;

    非簇头节点可以使用小功率和簇头节点通信;

    簇头节点可以对所辖区域节点数据进行融合,减少网络中传输的数据;

    簇头选举算法的设计,要求保证公平性

                  LEACH是第一个提出数据聚合的层次型路由协议,采用随机选择簇首的方式来避免簇首过度消耗能量;通过数据聚合有效地减少网络的通信量。LEACH协议的工作过程是一轮一轮地进行的,每一轮分为建立阶段和传输阶段。最重要的簇头选择。

     

                  建立阶段

                         节点运行算法,确定本次自己是否成为簇头;

    簇头节点广播自己成为簇头的事实;

    其他非簇头节点按照信号强弱选择应该加入的簇头,并通知该簇头节点;

    簇头节点按照TDMA的调度,给依附于他的节点分配时间片;

                  数据传输阶段

    非簇首节点负责采集数据,如果需要发送数据,就用最小的能耗发送给它的簇首节点。

    非簇首节点节点在分配给他的时间片上发送数据,在不属于自己时隙的期间可以进入睡眠状态以节省能耗,

    而簇首节点则必须始终处于接收状态。

    所有非簇首节点的TDMA时隙都轮过后,簇首节点对接收到的数据进行融合压缩,然后直接发送给Sink节点。

                 

     

                  LEACH协议优点:

                         优化了传输数所需的能量

                         优化了网络中的数据量

                  LEACH协议的缺点:

                         节点硬件需要支持射频功率自适应调整

                         随机选择簇头,无法保证簇头节点能遍及整个网络

                  LEACH协议的改进LEACH-C:

                         簇头由SINK节点指定

                         通过模拟退火算法选择簇头

     

     

           TEEN协议:

                  基本思想:

                         TEEN协议将无线传感器网络,分为主动型和响应型。

    主动型无线传感器网络持续监测周围的物质现象,并以恒定速率发送监测数据

    响应型无线传感器网络只是在被观测变量发生突变时才传送数据。响应型无线传感器网络更适合对时间敏感的应用

    TEEN和LEACH的实现机制非常相似,前者为响应型,后者属于主动型,TEEN采用LEACH-c的集中式簇头建立方法

    在TEEN协议中定义了两个门限的概念。

    硬门限:当传感器节点收集到的数据高于这个门限值时,节点开始向簇首节点汇报数据;

    软门限,当节点感应到的数据的变化值大于这个门限值时,节点开始向簇首汇节点报数据。

     

     

     

    根据阈值参数上报数据,提高重要数据的实时性   实时上报和周期性上报相结合

     

           TEEN和APTEEN的优缺点:

                  TEEN相比LEACH更适用于实时应用系统,对突发事件可以快速反应,但不适用于应用在周期性采集的应用系统中;

                  APTEEN结合响应型和主动型两种算法混合协议,通过计时器周期性发送数据,可以根据用户需要和应用类型改变周期和相关阈值,也能周期性采集数据,又能对突发事件做出响应。

                  他们两个的主要缺点体现在构建多层簇以及设置门限值在实现上比较复杂,基于属性命名的查询机制也会带来额外的开销。

     

    ③、基于地理位置信息的路由协议

           地理位置信息路由协议要求每个节点知道自己在网络中的位置,下列方法可确定节点位置

    GPS(Global Positioning System)

    超声波三角定位系统

    标定

    基于地理位置的路由协议一般分为两类:

    一类是使用地理位置协助改进其余路由算法,以用来约束网络中路由搜索的区域,减少网络不必要的开销,主要代表协议有LAR和GAF等

    另外一类是基于地理位置的路由协议,这一类协议直接利用地理位置来实现自己的路由策略,代表协议有GPSR和GEAR等

     

           GAF协议的基本思想——与路由相结合的节能策略:

                  节点在空闲、接收数据和发送数据时消耗的能量之比为1∶1.2∶1.7

                  GAF算法考虑到无线传感器网络中节点的冗余性特点,在地理位置信息的帮助下在保证网络正常流通的情况下,适当关闭一些节点来降低能量消耗,提高节点的生存时间,从而延长网络的生命周期

           在GAF路由算法主要机制包括:确定等价节点、轮换协商的算法和节点移动自适应算法。

    a)确定等价节点:GAF路由算法中,协议将整个区域分成若干个虚拟网格,虚拟网格中的任意一个节点都可以与相邻网格内的节点进行通信,因此对于每个网格中的节点来说都可以实现路由的连通,可以说是等价节点。

     

           b)分布式轮转协商算法

    网络节点有三种状态:休眠状态、发现状态和激活状态,各个状态之间的切换主要由定时器触发;

    节点休眠醒来后处于发现状态,通过发送发现报文让其他地理上相邻的等价节点进入休眠状态;发送了发送报文的节点转为激活状态

    只有处于激活状态的节点才参与数据转发,根据预期生存时间选择激活状态的节点做为路由节点

     

     

           c)节点移动的自适应算法

    处于激活状态的节点可能移动出其所在的网格,导致先前所在的网格可能没有一个激活节点,降低路由可靠性

    GAF通过预测并报告节点运动规律来解决移动节点造成的路由断裂问题

    GAF的每个移动节点根据移动速度、节点位置和网格大小预测它离开所在网格的时间,并且将此信息放入发现信息中

    其他等效节点的休眠时间由节点自身的缺省休眠时间和路由节点离开时间的最小值确定,确保在路由节点移出网格前有其他节点醒来,减少节点移动性带来的副作用

     

     

    GPSR协议的基本思想:

           GPSR协议直接使用地理信息实现路由,使用贪婪算法建立路由,当节点需要发送数据时,选择一个距离目标节点最近的节点作为转发数据的下一跳节点。该过程一直重复直到数据达到目标节点

    为避免局部优化问题,GPSR协议采用边界转发策略作为贪婪转发的补充

    优点

    采用局部最优的贪婪算法,不需要维护网络拓扑,路由开销小;

    可适用于静态和移动的WSN网络;

    缺点

    需要地理位置信息的支持;

    需要维护邻居节点位置信息;

     

     

    GEAR路由协议基本思想

           GEAR路由协议根据事件所在区域的地理信息,实现从Sink节点到事件所在地区节点的路径,这样就能实现Sink节点向某个特定区域发送数据,避免了泛洪似的全网广播数据,同时借鉴了SPIN中查询节点剩余能量值的方法,建立从Sink节点到目标区域的最优路径。

           前提

    已知目标区域的位置信息

    节点知道自己位置信息和剩余能量

    节点间无线链路是对称的

          

          

    GEAR路由协议的关键技术

    两个关键性技术问题

    向目标区域传送查询消息

    查询消息在事件区域内的传播

    选路依据

    节点到查询区域通信能量能耗

    节点本身的剩余能量

    最小代价节点为转发节点

     

           路由空洞问题

    邻居节点传输代价都比本地节点大;

    选择邻居节点中代价最小的作为转发节点;

    修改本地节点的转发代价;

     

           迭代地理转发:将目标区域分解为若干子区域、 向子区域的中心位置转发)

                   

           优点

    利用了位置信息,避免了查询消息的Flooding;

    考虑了消耗的能量和节点剩余能量,均衡消息;

    路径选择可达到局部最优;

    迭代地理转发对洪泛机制的补充;

    缺点

    可能出现路由空洞(局部信息)- 两跳信息;

    不适合在移动WSN使用

     

     

     

     

    四、移动SINK的无线传感器网络网络层协议

           基本思想

    通过移动Sink点克服网络中能耗和负载不平衡的现象

    通常需要知道节点的地理位置,需要节点有定位功能作为辅助

     

     

     

     

     

     

     

     

     

    第五章 传输层

    考点:

           特点、能否把TCP/IP适用于WSN?(掌握)

     

    概述:

           传输层是是最靠近用户数据的一层,主要负责在源和目标之间提供可靠的、性价比合理的数据传输功能。为了实现传输层对上层透明,可靠的数据传输服务,传输层主要研究端到端的流量控制和拥塞的避免,保证数据能够有效无差错地传输到目的节点。

     

     

    ***由于无线传感器网络自身的特点,TCP协议不能直接用于无线传感器网络,原因如下:

    TCP协议提供的是端到端的可靠信息传输,而WSN中存在大量的冗余信息,要求节点能够对接收到的数据包进行简单的处理。

    TCP协议采用的三次握手机制,而且WSN中节点的动态性强,TCP没有相对应的处理机制。

    TCP协议的可靠性要求很高,而WSN中只要求目的节点接收到源节点发送的事件,可以有一定的数据包丢失或者删除。

    TCP协议中采用的ACK反馈机制,这个过程中需要经历所有的中间节点,时延非常高且能量消耗也特别大;而WSN中对时延的要求比较高,能量也非常有限。

    对于拥塞控制的WSN协议来说,有时非拥塞丢包是比较正常的,但是在TCP协议中,非拥塞的丢包会引起源端进入拥塞控制阶段,从而降低网络的性能。

    最后一点也最重要,在TCP协议中,每个节点都被要求有一个独一无二的IP地址,而在大规模的无线传感器网络中基本上不可能实现的,也是没有必要的。

     

     

     

    ESRT:自适应调整协议,包括系统可靠性的检测以及是否拥塞和根据可靠性作出相应的调整;

           局限:SINK节点通信范围必须覆盖全网,硬件要求高,没有考虑节点优先级,可能会拥塞,不适用于大型网络

     

    PSFQ:逐跳可靠性保证协议,或快取慢充协议。快取即节点向它的邻居节点快速索取数据,慢充即等到所有的数据接收完整后再发送给它的下一跳节点。

    缓存机制:中间节点缓存接收到的数据;

    NACK确认机制:接收到数据包后,检查包序列号连不连续,找出丢失的包序号,广播NACK报文,获取丢包。

    逐跳错误恢复机制:节点接收到所有的数据报文后才想吓一跳发数据。

     

     

     

    PECR:是一种能够自适应调整的拥塞控制机制

    ①节点根据最小跳数协议初始化自己的路由表信息,确定每个节点的下一跳节点。

    ②节点周期性地检测缓存占用率并将其作为拥塞信息写入反馈数据包中,并向其邻居节点发送此报文。

    ③源节点收到下游节点反馈的拥塞信息后,立即将此拥塞信息写入本地缓存的邻居节点拥塞表内。

    ④进入分流过程,节点将检测自己选择的下一跳节点是否满足拥塞度和剩余能量值的要求。

     

    CODE:基于逐跳的拥塞控制协议,采用信道监听和缓存队列检测相结合的方式检测拥塞,开环控制机制,闭环调节反应机制。

     

     

    RCTP:针对可靠性传输协议CTP(汇聚树协议)进行的改进,跨层分簇,包括拥塞检测和拥塞后的实施调度;缓存检测:实时队列和非实时队列任意一个队列缓存过半时,认为拥塞,发生拥塞后调用相应的实时调度方法缓解拥塞。

     

     

     

     

     

     

     

     

     

     

    第六章 通信标准

    考点:

           关系、概念(掌握)

     

    ①、IEEE 802.15.4 标准(LR WPAN 低速无线个人局域网)

           能量消耗少,结构简单且容易实现的无线通信网络协议,它主要致力于解决无线连接在能量值和网络吞吐量低的网络中应用。

    在不同的载波频率下实现20 kbps、40 kbps、100 kbps以及250 kbps四种不同的传输速率;

    支持星状和点对点两种网络拓扑结构;

    在网络中使用两种地址格式,16位和64位地址,16位地址由协调器分配,64位地址被用于全球唯一的扩展地址;

    采用可选的时槽 保障(GTS)机制;

    采用冲突避免的载波多路侦听技术(CSMA/CA);

    支持ACK反馈机制,确保数据的可靠传输。

     

    根据设备所具有的通信能力和硬件条件分为全功能设备和精简功能设备。

    该网络应用场景分为:

           星状网络:整个网络数据传输都要经过网络协调器控制,其余各个终端设备只能与网络协调器数据交换。

           点对点网络:只要通信设备在对方无限辐射范围内就可以通信。

     

    该网络协议存在于物理层和数据链路层之间,物理层是由射频收发器和底层控制模块组成,链路层为高层访问提供了访问物理信道的服务接口。

     

     

    ②、ZIGBEE:

           扩展了IEEE802.15.4 的网络层和应用层

    ZigBee协议中定义了三种设备:ZigBee协调器、ZigBee路由器和ZigBee终端设备:

    ZigBee协调器,它负责建立并启动一个网络,包括选择合适的射频信道、唯一的网络标识符等一系列操作。

    ZigBee路由器作为远程设备之间的中继器来进行通信,能够拓展网络的范围,负责搜寻网络,并在任意两个设备之间建立端到端的传输。

    ZigBee终端设备作为网络中的终端节点,负责数据的采集。

     

    ZigBee的应用层由三个部分组成:应用支持子层、应用层框架和ZigBee应用对象(ZDO)。

    应用支持子层为网络层和应用层通过ZigBee设备对象与制造商定义的应用对象使用的一组服务提供了接口,该接口提供了ZigBee设备对象和制造商定义的应用对象使用的一组服务,通过数据服务和管理服务两个实体提供这些服务。

    应用框架可为驻扎在ZigBee设备中的应用对象提供活动的环境。

    设备对象描述了一个基本的功能函数,这个功能在应用对象、设备(Profile)和APS之间的提供了一个接口。 ZDO位于应用框架和应用支持子层之间,可满足所有在ZigBee协议栈中应用操作的一般需要

     

    ③、蓝牙技术

    蓝牙采用分散式网络结构以及快跳频和短包技术,支持点对点及点对多点通信,工作在全球通用的2.4 GHz ISM频段,其数据速率为1 Mbps,采用时分双工传输方案实现全双工传输。

    蓝牙优势:

    频段免费、设备范围广、易于使用、抗干扰能力强、可以同时传输语音和数据

     

     

     

     

     

    第七章 时间同步技术考点

    考点:

    要解决的问题(了解)

           区分传统时间同步(了解)

           RBS、TPSN(掌握)

           区分新型时间同步技术(了解)

     

    三种深度的同步:

    时序确定、判断事件发生的先后顺序;

    相对同步,每一个节点维护本地时钟

    绝对同步,所有节点同步

           外同步:参考时间来自外部

           内同步:参考时间来自内部某个节点

     

     

    无线传感器网络时间同步协议必须要解决三个方面的问题:

    同步的误差要尽可能地小,这样才能保证整个网络间节点应用的正常进行

    因为无线传感器网络节点的电池不可替换,因此协议要尽可能地简单,功耗要低,以尽可能地延长网络的生命周期

    具有可扩展性,随着无线传感器网络规模的扩大,时间同步协议要同样有效

    稳定性

     

    时间同步的两个重要的时间参数:

    时钟偏移:在真实时刻t时定义时钟偏移为c(t)−t,即本地时间与真实时间的差值。

    时钟漂移:在真实时刻t时定义时钟漂移为ρ(t)=r(t)−1,即本地时间变化速率与1的差值。

    在节点的两种时间计数方式:

    硬件计数模式:即利用晶振来实现时间的计数

    软件时钟模式:采用虚拟的软件时钟来实现时钟的计数

     

     

    NTP:分层,每一层向上一层服务器同步时间

     

    DMTS:

    接收者时间最后改为:t0+nΔt+t2−t1

     

    能耗小,但是没有考虑传播延迟、编/解码的影响,对时钟漂移也没有考虑,同步的精度不是很高,还有待进一步的改进。

     

     

    RBS:假设有N个节点组成的单跳网络,1个发送节点,N−1个接收节点,发送节点周期性地向接收节点发送参考报文,广播域内的接收节点都将收到该参考报文,并各自记录收到该报文的时刻。接收者们通过交换本地时间戳信息,这样这一组节点就可以计算出它们之间的时钟偏差。

     

    TPSN:

                  两个阶段:

                  层次发现阶段:

    级别发现分组包含发送节点的ID和级别。根节点是0级节点,在根节点广播域内的节点收到根节点发送的分组后,将自己的级别设置为分组中的级别加1,即为第1级,然后将自己的级别和ID作为新的发现分组广播出去。

    当一个节点收到第i级节点的广播分组后,记录发送这个广播分组的节点的ID,设置自己的级别为i+1。这个过程持续下去,直到网络内的每个节点都具有一个级别为止。如果节点已经建立自己的级别,就忽略其他的级别发现分组。

           时间同步阶段:

    建立层次之后,相邻层次之间的节点通过双向报文机制来进行时间同步,假设节点A是第i层的节点,节点B是第i-1层的节点,根据TPSN报文交换协议,我们规定T1和T4为节点A的时间,T2和T3为节点B的时间,节点A在T1向节点B发送一个同步报文,节点B在收到该报文后,记录下接收到该报文的时刻T2,并立刻向节点A发回一个应答报文,将时刻T2和该报文的发送时刻T3嵌入到应答报文中。当节点A收到该应答报文后,记录下此时刻T4。我们假设当节点A在T1时刻,A和B的时间偏移为Δ,因为T1到T4两个报文发送的时间非常短,我们可以认为Δ没有变化,假设报文的传输延迟都是相同且对称的,均为d,那么有

                         T2=T1+Δ+d   T4=T3−Δ+d,

    这两个方程联立可解得:

           Δ=[(T2-T1)-(T4-T3)]/2,  d=[(T2-T1)+(T4-T3)]/2

    在T4时刻,节点A在本地时间上面加上一个偏移量Δ,A和B就达到了同步。

    从双向同步协议的同步过程中可以看出,在TPSN协议中,当双向报文的传输完全对称时其精确度最高,即同步误差最小。另外TPSN的同步误差与双向报文的传输延迟有关,延迟越短,同步误差越小。

     

     

    FTSP:

    FTSP(泛洪时间同步协议)也采用单个广播消息实现发送节点与接收节点之间的时间同步,采用同步时间数据的线性回归方法估计时钟漂移和偏差。综合考虑了能量感知、可扩展性、鲁棒性、稳定性和收敛性等方面的要求。FTSP算法实现步骤如下:

    (1)FTSP算法在完成SYNC字节发射后给时间同步消息标记时间戳并将其发射出去。

    (2)接收节点记录SYNC字节最后到达时间,并计算位偏移。在收到完整的消息后,接收节点计算位偏移产生的时间延迟,这可通过偏移位数与接收速率得出。

    (3)接收节点计算与发送节点问的时钟偏移量,然后调整本地时钟和发送节点时间同步。

     

    比较:

    1.精度方面

    RBS协议:因为无线信道的广播特性,使得发送节点发出的消息相对所有节点而言是同时发送到物理信道上的,相当于将消息传递过程中两项最不确定的时延被去除了,所以能够得到较高的同步精度。

    TPSN协议:在网络传输的时延中,访问时延的不确定性是最高的。为了提高两个节点之间的时间同步精度,TPSN协议直接在MAC层记录时间信标,这样可以有效地消除发送时延、访问时延、接收处理时延所带来的时间同步误差。并利用双向消息交换计算消息的平均延迟,提高了时间同步的精度。

    FTSP协议:采用在MAC层记录时间信标,细分消息传输中的时间延迟对这些延迟进行补偿,利用线性回归估计时间漂移等措施来降低时间同步误差。

     

    2.收敛性方面

    RBS协议:发送参考广播的节点是预先选定的,其他节点接收到参考广播消息后,就开始同步的过程。考虑到通信冲突,在几个同步周期后,全网就可以达到时间同步,收敛时间也比较短。

    TPSN协议:这种同步方法的消息传递机制分为两个过程,包括分层阶段和同步阶段,因此其收敛时间较长。

    FTSP协议:该协议的根节点选择过程是伴随时间同步一起进行的,根节点的选择不会对收敛性造成影响,在几个同步周期后,全网就能达到时间同步,收敛时间也比较短。

     

    3.扩展性方面

    RBS协议:在全网达到同步后,新节点的加入不会影响到参考广播节点的地位,也就不会对全网的结构造成影响。但是,加入新的参考广播节点会使得情况变得复杂,必须考虑处于不同广播域内的节点达到同步的问题。对于多跳网络的RBS协议需要依赖有效的分簇方法,保证簇之间具有共同的节点,以便簇间进行时间同步。

    TPSN协议:从分层过程可以看出,新节点加入后会对网络的拓扑结构造成很大的影响,应此,该协议的扩展性很差,这也是这个协议最大的缺点之一。

    FTSP协议:如果加入的是ID号最小的节点,该节点首先使自己与网络达到同步,然后再进行根节点选择,不会影响网络时间同步。如果不是ID号最小的节点,该节点只需要进行时间同步并广播时间同步消息。

     

    4.鲁棒性方面(健壮性)

     

    RBS协议:由RBS协议的同步原理可以看出,节点失效或网络通信故障不会破坏整个拓扑结构,每个节点都有大量的冗余消息来保证时间同步。但是参考节点失效就会影响到该节点广播域内所有节点的同步。该协议具有较好的鲁棒性。

     

    TPSN协议:当某个节点失效,该节点以下的节点就有可能接收不到时间同步消息,这样就会造成连锁反应,影响到该节点所有的后续节点的时间同步。全网的时间同步会受到个别节点的影响,鲁棒性很差。

     

    FTSP协议:如果是根节点失效,那么其他节点就会开始根节点选择的过程,重新选出一个根节点,这在段时期内会破坏时间同步,但全网很快就能重新达到同步。如果是其他节点失效,由于大量冗余消息的存在,个别节点不会影响全网时间同步。FTSP协议也具有良好的鲁棒性。

     

    5.能耗方面

    可以利用网络中的节点在一次时间同步中平均接收和发送消息的次数来简单的估计时间同步协议的能耗。

    RBS协议:要实现两个节点之间的时间同步,节点需要接收一次广播消息,然后再交换一次时间同步消息,平均需要2次消息发送和3次消息接收。协议的能量消耗较大。

    TPSN协议:由于这个方法采用的是类客户/服务器模式,所以实现一次时间同步,节点平均需要2次消息发送和2次消息接收,协议的能量消耗相对较小。

    FTSP协议:在该协议中,节点接收到时间同步消息后,使得节点本地时间与全局时间达到同步,然后形成新的时间同步消息并发送出去。每次同步,节点平均需要1次消息发送和1次消息接收,协议的能量消耗是最小的。

     

     

     

    两个新的时间同步技术试图解决传统时间同步技术中的同步积累误差和可扩展性问题:

    协作同步技术

    萤火虫同步技术

     

     

     

    Peskin模型和M&S模型模拟了萤火虫自同步(Self-Synchronization)方式,在理论上证明了振荡器节点能够达到同步,然而,由理论所引导而做出的一些假设,应用于无线传感器网络,在实现上却存在五点局限性:

    当一个节点激发时,它的邻居节点不能即时地获取这个时间

    节点不能即时地对激发事件做出反应

    节点不能精确地并且即时地计算出f和f−1

    所有的节点没有相同的时间周期T

    节点不能从它的邻居节点观察到所有的事件(具有信息损耗)

     

     

    与其他协议相比,萤火虫同步算法具有独特的优点:

     同步可直接在物理层而不需要以报文的方式实现;

     由于对任何同步信号的处理方式均相同,与同步信号的来源无关,因此可扩展性以及适应网络动态变化的能力很强;

     机制简单,不需要对其他节点的时间信息进行存储。

     

     

     

     

     

     

     

     

     

     

    第八章 WSN节点定位技术

    考点:

    定位技术原理和区分(了解)

     

    8、1 节点定位技术概述

           WSN节点定位:依靠网络中少量位置已知的节点,通过邻居节点间有限的通信和某种定位机制确定网络中所有未知节点的位置。

           节点定位在实际中包含:

                  自定位:确定节点自身在系统中的位置

                  目标定位:确定目标节点在系统中的位置

          

                  一些概念:

                  信标节点:已知自身位置信息的节点,可通过GPS定位设备或手工配置、确定部署等方式预先获取位置信息,为其他节点提供参考坐标。

    未知节点:信标节点以外的节点统称为未知节点,也有文献称为盲节点。

    邻居节点:一个节点通信距离范围内的所有节点的集合。

    跳数:两个节点之间跳段的总数。

    跳距:两个节点之间各跳段的距离之和。

    节点连接度:节点可以探测发现到的邻居节点个数。

    网络连接度:所有节点的邻居个数取平均值,可反映传感器配置的密集程度

     

    节点定位要求:

                  传感器网络的定位算法通常需要具备以下特点:

    自组织性:传感器网络的节点随机部署,不依赖于全局基础设施协助定位;

    健壮性:传感器节点的硬件配置低,能量有限,可靠性较差,定位算法必须能够容忍节点失效和测距误差;

    节能性:尽可能地减少算法中计算的算法复杂度,减少节点间的通信开销,以尽量延长网络的生存周期;

    分布式:无线传感器网络通常是大规模部署网络,节点数目多,定位任务将不会是单个节点所能承担的,这就需要定位算法具有一定的分布式,把任务分派到各个节点;

    可扩展性:无线传感器网络中的节点数目可能是成千上万甚至更多,为了满足对不同规模的网络的适用性,定位算法必须具有较强的可扩展性。

     

     

    8、2 节点定位技术研究状况和发展

           作为一种全新的技术,无线传感器网络具有许多挑战性的研究课题,而定位就是其中之一,定位也是大多数应用的基础和前提

    传感器节点的微型化和有限的电池供电能力使其在节点硬件的选择上受到很大的限制,低功耗是其最主要的设计目标。必须针对密集性,节点的计算、存储和通信等能力都有限的特定场合设计有效的低功耗定位算法

    近十年来,无线传感器网络自身定位问题研究有了许多新颖的解决方案和思想,但是每种系统和算法都是用来解决不同的问题或支持不同的应用的,它们用于定位的物理现象、传感器设备的组成、能量需求、基础设施和时空的复杂性等许多方面有所不同。

    对现有的WSN定位研究成果研究比较发现,没有一种定位方案能在有效减少通信开销、降低功耗、节省网络带宽的同时获得较高的定位精度。而且大部分停留在仿真和实验阶段。因此,该领域还有待更多的人提出更好的方法,以求更好地解决定位问题,使得无线传感器网络能够真正在实际生活中得到广泛的应用。

     

    8、3 节点定位技术关键问题

           1.定位区域与精确度

    定位区域与精确度是传统定位方法和无线传感器网络定位都具有的衡量指标,而且定位区域和精度一般都是互补存在的,定位区域越大,意味着精度越小。

    2.实时性

    实时性是定位技术的另外一个关键指标,实时性与位置信息的更新频率密切相关,位置信息更新频率越高,实时性越强

    3.能耗

    能耗是无线传感器网络独有的一个衡量指标。在无线传感器网络中,节点的电能靠电池来供应,电池是不可替换的,因此节省能量就成了无线传感器网络中一个重要的问题。

    另外,还有一些小的方面来衡量无线传感器网络定位技术的好坏,如定位技术的扩展性、鲁棒性和节点带宽的占用等。

     

    8、4 基于测距的定位技术

     

                  已知几个节点的位置,求另外节点的位置:

                         三边定位法;角度定位法;

                  一般有三种算法可以测量两个节点之间的距离:

                         根据接收信号的强度来计算距离;RSSI

    根据信号传播时间或者时间差来计算距离;TOA

    根据接收信号相位差定位。TDOA

                   

                 

                  常用的角度定位方法有:已知两个顶点和夹角的射线确定一点,以及已知三点和三个夹角确定一点。

     

     

    8、5 无需测距的定位技术

     

           ①、基于连通性的定位

                  连通性(Connectivity)是指两个节点是否连通。基于连通性的定位可以根据一个节点能否成功解调其他节点传来的数据包作为依据。

           ②、基于跳数的定位

                  跳数原理就是对信标节点信息洪泛的过程进行跳数统计,通过统计未知节点与信标节点之间的跳数,然后根据信标节点之间的距离和跳数估算出全网每一跳的平均距离,二者相乘,即可得到两个节点之间的距离。

     

    质心定位算法:

    APTI定位算法

    DV-Hop定位算法

           凸优化方法

     

     

     

     

     

    8、6 协作定位技术

    钢性理论概述:

           刚性,即在不考虑物质特性的理想条件下任何两个连接点之间的欧氏距离不随其运动状态改变的特性。

     

     

    协作定义原理:根据网络局部拓扑结构采用模式匹配的方法自组的进行节点间通信连接,根据与未知节点连通的导标节点个数和形式,通过几何约束条件判断该未知节点是否可以与邻居节点导标构建最简单元定位协作体或准定位协作体,然后在最简单元定位协作体的基础上,扩展成更多节点的定位协作体。

     

     

     

     

     

     

     

     

    第九章 容错设计技术

    考点:

           概念(了解)

           失效、故障、容错、差错(区分了解)

           精度?上行、下行模式(了解)

     

    9、1 容错技术概述

           容错就是指当由于种种原因在系统中出现了数据、文件损坏或丢失时,系统能够自动将这些损坏或丢失的文件和数据恢复到发生事故以前的状态,使系统能够连续正常运行的一种技术。

     

    失效:失效就是某个设备停止工作,不能够完成所要求的功能。

     

    故障:故障是指某个设备能够工作,但是并不能按照系统的要求工作,得不到应有的功能,它与失效的主要区别就是设备还在工作,但是不正常。

     

    差错:差错是指设备出现了的不正常的操作步骤或结果。

     

    故障->差错->失效

     

    容错技术分类:

           ①、故障避免:避免或预防故障的发生

           ②、故障检测:用不同的策略来检测网络中的异常行为

           ③、故障隔离:对故障节点进行隔离,以免影响现有网络

           ④、故障修复:网络故障后的一项补救措施

     

     

    9、2 容错设计模型

    WSN故障三个层级:(部件级、节点级、网络级)

    部件级故障是指此类故障节点能够正常通信,但其测量值是错误的,会影响网络分析处理数据的结果;

    节点级故障是指故障节点不能与其他节点进行正常的通信,会影响网络连通性和覆盖性;

    网络级故障是指网络通信协议或协作管理方面的问题或其他原因造成的较大规模的故障,导致整个网络不能正常工作。

          

    容错设计模型标准:

    (1)能效性:这里主要考虑传感器节点在数据采集、数据处理、通信三方面的能耗。

    (2)故障诊断精度:一般地,故障诊断精度是指一次故障诊断过程完成后,诊断状态与实际状态相同的节点占总节点数的百分比。有时候,故障诊断精度也被细分为故障识别率和误报率两个指标。

    (3)故障诊断执行时间:在执行故障诊断过程中节点之间要进行协作判断,也就是处于激活状态的节点数目会比较大,如果故障诊断过程持续比较久会给网络带来较大的能耗负担。

    (4)恶劣环境中的故障诊断精度:在一些特殊的应用中,由于环境、自然灾害或人为因素的影响,网络中的故障节点分布不均匀,可能在局部区域出现故障节点聚集的现象,这种现象会影响故障诊断机制的性能表现,一个好的故障诊断机制应该能有效地应对这样的情况。

     

    9、3 WSN可靠性分析

     

           物理层是无线传感器网络的最底层,主要负责信息的发送、编/解码功能,其主要可靠性都是来自于系统硬件.

     

    数据链路层主要负责对物理层发送的数据进行错误检测,将物理层的数据错误率降低到阈值以下,采用反馈机制来保证它的可靠性

    网络层的主要功能是负责节点间路由的选择及维护。可分为两种模式:

    任由节点泛洪式地选择自己的路由,不加任何干涉,泛洪就是这种模式的典型协议,这种模式的好处就是基本上不涉及算法,节点接收到信息之后不用维护本地路由表,直接广播数据包即可,因为多路径传输数据包到汇聚节点,所以具有很高的容错性,但由此带来了大量冗余信息传输,容易造成网络拥塞,耗费大量能量,因此不适宜用在无线传感器网络中。

    另外一种模式就是局部多路径传输协议,当网络正常时,网络以一跳最优路径进行数据的传输,这样能最大限度地节省能量,如最小跳数协议。当网络发现某节点发生拥塞时,调控节点进行多径分流,以此来降低节点的通信负载,保证系统的可靠性

     

    传输层可靠性

         在无线传感器网络中,理想的传输层能支持可靠的信息传递和提供有效的拥塞控制,以此来延长无线传感器网络的生命周期。可靠性保证分为两种,一种是事件的可靠性,另一种是数据包的可靠性,无线传感器网络中一般采用基于事件的可靠性,因此只需要数据传输的可靠性达到一个保证事件传输的阈值即可。

     

    无线传感器网络中数据传输分为两种形式:

    上行模式,即从传感器节点到汇聚节点,这是感应源节点到汇聚节点而形成的一股数据流,目的是保证汇聚节点能够监测到感兴趣区域的事件情况。

    下行模式,即从汇聚节点到传感器节点的数据传输,在这种模式中传输的不再是节点采集的信息,而是汇聚节点给予感应区域内的控制或者查询消息,它可能用于调整整个网络的路由,避免网络的拥塞;也可能用于反馈消息的正确接收或者查询某个特定区域的信息,规定其优先级等。

     

     

     

    9、4 WSN故障检测和诊断

    基于空间相关的故障检测:

           空间相关性:是指无线传感器网络中相邻节点的同类传感器之间所测量的值通常有很相近的特性。

    (1)需要地理位置信息。在地理位置信息已知的情况下,利用三个可信节点实现三角法检测感应器故障。

                  (2)无须地理位置信息。这类检测通常是通过侦听邻居数据来判断自己测量值是否正确的,判断策略可分为多数投票策略、均值策略和中值策略。

     

                  多数投票策略是通过与邻居节点测量值进行比较,得到与自己的测量值相同或差距在允许范围内的邻居测量值个数,如果个数超过邻居数目的一半,则判定自己的测量值为正确的,否则就是错误的。

     

    均值策略首先计算邻居测量值的平均值,然后比较这个均值和自己的测量值,如果它们差距在允许的范围内,则认为自己的测量值为正确的。

     

    中值策略是利用邻居测量值的中值与自己的测量值比较,在很大程度上避免了错误的邻居节点测量值对测量精度的影响,在有很多邻居节点测量值错误的情况下,节点仍然能正确地判断出自己的测量值是否正确。

     

     

     

    基于贝叶斯信任网络:

     

     

    9、5 WSN自恢复策略

    容错节点是一种可以替换失效活动节点的睡眠节点或冗余节点。活动节点失效会造成某些邻居节点的连接断开,在它失效时,其邻居节点可以通过指定的容错节点来通信。

     

    节点失效会造成某些区域不被覆盖,这时需要采取措施来弥补覆盖空洞。节点覆盖区域定义为它的整个感知区域除去与其他节点重叠的部分。失效节点的覆盖区域需要其他节点来弥补。假设网络中的节点具有移动能力,它把覆盖修复过程分为四个阶段

    (1)初始化阶段:节点计算自己的覆盖区域、每个覆盖区域对应的移动区域。

    (2)恐慌请求阶段:垂死节点广播求助消息。

    (3)恐慌回应阶段:垂死节点的邻居节点收到求助消息后计算如果自己移动到垂死节点的移动区域,是否会影响到自身的覆盖区域,如果不影响则给求助节点返回消息。

    (4)决策阶段:垂死节点根据收到的回应信息,决定让哪个节点移动。

     

     

     

     

     

     

    第十章 服务质量保证

    考点:

           QoS含义、功能(了解)

     

     

    10、1 QOS概述

           含义:

                  从应用的角度看,QoS代表用户对于网络所提供服务的满意程度;

    从网络的角度看,QoS代表网络向用户所提供的业务参数指标。

     

           质量标准:

    (1)可用性:指综合考虑网络设备的可靠性与网络生存性等网络失效因素,当用户需要时即能开始工作的时间百分比。

    (2)吞吐量:又称为带宽,是在一定时间段内对网络流量的度量。一般来说,吞吐量越大越好。

    (3)时延:指一项服务从网络入口到出口的平均经过时间。许多实时应用,如语音和视频等服务对时延的要求很高。

    (4)时延变化:指同一业务流中所呈现的时延不同。高频率的时延变化称为抖动,而低频率的时延变化称为漂移。

    (5)丢包率:指网络在传输过程中数据包丢失的比率。造成数据包丢失的主要原因有网络链路质量较差、网络发生拥塞等。

     

     

     

     

    10、2 发展现状

     

    ①、应用层QoS保障技术

    应用层QoS需求是由应用设计者和用户提出的。QoS可定义为系统生命期、查询响应时间、事件检测成功率、查询结果数据的时间空间分辨率、数据可靠性和数据新颖度。

    ②、数据管理层QoS保障技术

    分布式传感器网络是由大量廉价的传感器节点组成的一个自组织系统,为了获得期望的服务质量,实现响应时间和资源需求,传感器节点必须互相协作,实现高效的信息采集和分发策略。

    ③、数据传输层QoS保障技术

    PSFQ采取快吸慢取的方式,能够为具有不同可靠性需求的应用提供简单、健壮和可扩展的传输协议。

    ESRT[6]是一个新颖的数据传输方法,用最少的能量获得可靠的事件检测结果,包含一个阻塞控制部件,既保证可靠性又节省能量。

    上述文献主要研究的是数据传输层的QoS保障机制,QoS往往定义为数据传输的可靠性和实时性,同时要考虑能源高效性。

    ④、网络层QoS保障技术

           在WSN的体系结构中,网络层是提供QoS支持的主要部分。作为在网络层支持QoS的载体,QoS路由协议的好坏对无线传感器网络的性能有着重要的影响。路由协议负责将数据分组从源节点通过网络转发到目的节点。

     

                  路由协议挑战:

                         网络动态变化、资源严重受损、对多种业务QOS支持、能量和QOS平衡、可扩展性

     

    ⑤、连通覆盖层的QoS保障技术

           保证网络的感知覆盖度和连通度是传感器网络特殊的QoS需求,目前已有许多相关的研究工作。

    ⑥、MAC层的QoS保障技术

           在WSN中,MAC协议决定无线信道的使用方式,在传感器节点之间分配有限的通信资源,对WSN的性能有较大的影响。目前,研究人员为无线网络提出一些基于冲突和载波监听的MAC协议,目标是最大化系统吞吐量,并未提供实时性保证。

    ⑦、交叉层支持QoS的中间件

            。基于服务的中间件用于接收用户的QoS需求,以高效的可扩展的方式保障应用的实时性要求,利用节点的冗余保证容错,并且支持多Sink节点的多种QoS需求。

     

     

     

    10、3 关键问题

    资源严重受损、以数据为中心,非端到端的通信模式、数据高度冗余、流量非均匀分布、节点密集分布无线多跳传输、多用户、多任务并发操作,多类别数据流量、可扩展性

     

     

    10、4 感知QOS保证

    无线传感器网络感知QoS,即无线传感器网络中传感器节点对监测区域的感应,监控的效果。

    无线传感器网络的可能应用多种多样,根据监控目标的几何性质可将覆盖控制问题分为点(目标)覆盖、区域覆盖及线覆盖三类

     

    ●为区域中存在的监控目标,○为休眠节点,●为工作节点。

     

    感知模型

     

    感知原型:节点的传感及通信范围难以保证为某一固定半径的圆,传感与通信具有方向性,且随着距离的增大,监控准确度和概率都相应减小。

    0-1感知模型:通过研究区域内圆盘覆盖来获取WSN覆盖控制策略,具有感知的阶跃性。

    概率感知模型:去除方向性的同时,保留了距离对感知精度的影响,随着传感器与监控目标间距离的增大,传感器对目标的感知概率也逐渐减小直至无法感知。

     

     

     

    虽然WSN覆盖控制研究已经取得了一定的成果,但是仍有很多问题需要解决,集中体现在以下几点:

     

    感知模型种类的完善。

    三维空间的覆盖控制。

    提供移动性的支持。

    符合WSN与Internet交互的相应WSN覆盖控制方案。

    开发和设计更多结合WSN覆盖控制的应用。

     

     

     

     

     

     

    10、5 传输QOS保证

    在无线传感器网络中评价传输服务质量的关键指标如下。

    传输成功率。

    时延。

     

    传感数据包能否实现端到端的可靠传输是网络能否成功实施并应用的一个重要条件。在网络中,造成数据包丢失的原因主要有三个方面。

    (1)无线传感器网络所使用的无线信道与有线链路相比有更大的不稳定性以及更高的误码率,很容易受到周围环境噪声的影响造成数据包的丢失。另外在无线传感器网络中,传感器节点的分布密度非常高,不同节点在发送数据时极易发生信道竞争冲突以及碰撞造成数据包丢失。

    (2)当无线传感器网络中发生拥塞时,拥塞节点缓存溢出造成数据包丢失。

    (3)接收节点因为数据包到达过快来不及处理造成数据包丢失。

     

     

    目前来说,无线传感器网络为了保证稳定传输提出了几种可靠性机制:

     

    反馈确认机制。

     

    冗余数据保证机制。

     

    多路径传输机制。

     

    FEC前向纠错码机制。

     

     

     

     

     

     

    第十一章 网络管理

    考点:

           区分几种管理系统(了解)

     

     

    11、1 网络管理概述

           网络管理是指对网络的运行状态进行检测和控制,使其有效可靠安全经济的提供服务;

           两个任务:

                  对网络的运行状态进行监测;

                  对网络的运行状态进行控制

     

           简单来说,网络管理是对网络中的资源进行合理的分配和控制,或者当网络运行出现异常时能及时响应和排除异常等各种活动的总称,以满足业务提供方和网络用户的需要,使得网络有效资源可以得到最有效的利用,使得整个网络的运行更加高效,能够连续、稳定和可靠地提供网络服务。

     

    运行:针对向用户提供的服务进行,面向网络整体进行管理,

    控制:网络的控制管理针对向用户提供有效的服务和为满足提供服务的质量要求进行的管理活动

    维护:为了保障网络及其设备的正常可靠连续运行而进行的一系列管理活动,包括故障检测、定位和恢复,对设备单元的测试

    提供:针对电信资源的服务装备进行的一系列网络管理活动,为实现某些服务提供某些资源和给用户提供某些服务

     

     

     

     

     

    11、2 发展现状

    挑战:

           无线传感器网络的管理模型必须能适应不同的应用,并且在不同的应用间进行移植时修改的代价最小,即具有一定的通用性。

           无线传感器网络大多按照无人看管的原则部署。

           无线传感器网络资源受限。

     

     

    11、3 关键问题

     

    网络管理原则:

           高效的通信机制

           轻量型的结构

           智能自组织的机制

           安全、稳定的环境

     

    11、4 典型网络管理系统

     

    集中式网络管理系统:

    BOSS:

          

           Tiny—DB:

                  基于查询的WSN数据管理系统,它从节点收集相关数据,调度各个节点对查询进行分布式处理,将查询结果通过基站返回给用户。

     

     

    层次式网络管理系统:

           RRP:按照供应链策略,RRP将无线传感器网络分为几个功能区,针对功能区各自的特点采用不同的路由模式,各个功能区之间相互协作以达到最佳的网络性能,并尽量降低能量消耗。RRP中游三个功能区:生产区、运输区以及仓储和服务区,各个区之间的节点的角色和任务各不相同。

     

           SNMP:定义描述网络当前状态的网络模型和一些列的网络管理功能;设计提取网络状态和维护网络性能的一系列算法和工具

     

     

    分布式网络管理系统:

           基于移动AGENT的数据管理:基于移动Agent技术的无线传感器网络管理模型,该模型采用数据本地存储的方式,让每个传感器器节点把自身的特征数据和感知数据存储在自身节点上,使数据传输的开销降低到最小;再使用移动数据查询代理在合理的节点上采集数据,便可以有效地满足查询的需要。

          

                  TinyCubus:一种自适应的传感器网络跨层管理框架,TinyCubus包含三个部分:跨层结构、配置引擎、数据管理结构。

     

                  跨层结构为要进行跨层交互(如优化时需要其他模块的信息,通过对高层组件的回调执行特定应用的代码等)的模块提供了一个通用的参数化接口。

     

    配置引擎基于传感器节点的角色进行代码分发,并支持动态安装程序代码,其目的是支持系统和应用组件的配置,包括拓扑管理器和代码分发程序。

     

    数据管理结构提供了一组标准数据管理组件和系统组件,并根据当前系统中的信息选择最恰当的一些组件用于管理。数据管理结构用一个立方体定义,包含三个维度:

     

    优化参数,如能量、通信延迟和带宽;

    应用需求,如可靠性;

    系统参数,如节点移动性和网络密度。

    展开全文
  • 【JAVA面试】java面试题整理(3)

    千次阅读 2018-10-28 12:50:13
    TCP的逻辑通信信道是全双工的可靠信道,UDP则是不可靠信道     4、 项目是怎样预防sql注入的 回答:用的是mybatis,sql语句中用#{},#{}表示一个占位符号,通过#{}可以实现preparedStatement向占位符中...

                                         java面试题整理(3)

    JAVA常考点3

    目录

    1. 讲下JAVA的运行时区域 1

    2、简单说下垃圾回收机制 2

    3、TCP和UDP的区别 7

    4、项目是怎样预防sql注入的 7

    5、 MySQL存储引擎中的MyISAM和InnoDB区别 7

    6、B树与B+树简明扼要的区别 11

    6、 解决哈希冲突的三种方法(拉链法、开放地址法、再散列法) 14

    7、forward(转发)和redirect(重定向)有什么区别 16

    8、set、list、map 16

    9、 HashMap、Hashtable、ConcurrentHashMap的原理与区别 19

     

     

     

     

     

    1. 讲下JAVA的运行时区域

     

    回答:运行时数据区整体分为两类 线程私有和线程共享。

     

    线程私有的包括:

     

    (1)程序计数器

     

    若正在执行的是java方法,则计数器记录的是正在执行的字节码指令的地址

    若正在执行的是native方法,则计数器为空

    该区域是唯一一个不会导致outofmemoryError的区域

     

    (2)虚拟机栈

     

    描述的是Java方法执行的内存模型:每个方法都会创建一个栈帧用于存储局部变量表,操作数栈,动态链接,方法出口等信息

     

    局部变量表存放了编译期可知的基本数据类型,对象引用,和returnAddress类型(指向一条字节码指令地址),局部变量表的内存空间在编译器确定,在运行期不变

    可导致两种异常:线程请求的栈深度大于虚拟机允许的深度-StackOverflowError;虚拟机无法申请到足够的内存-OutOfMemoryError

     

    (3)本地方法栈

    和虚拟机栈类似,但它是为Native方法服务的

     

     

    线程共享的包括:

     

    (1)堆

     

    java堆是被所有线程共享的内存区域,在虚拟机启动时创建,用来分配对象实例和数组

    堆是垃圾回收器主要管理的区域,堆可分为新生代和老年代

    从内存分配角度看,堆可划分出多个线程私有的分配缓冲区(TLAB)

    大小可通过 -Xmx 和 -Xms 控制

     

    (2)方法区

     

    用来存放虚拟机加载的类信息,常量,静态变量,即时编译器编译后的代码等信息

    GC会回收该区域的常量池和进行类型的卸载 *运行时常量池

    ♣ Class文件的常量池用于存放编译期生成的各种字面量和符号引用,这部分内容将在类加载后存放在运行时常量池中

    ♣ 还把翻译出来的直接引用也放在运行时常量池中,运行时产生的常量也放在里面

     

     

     

    2、简单说下垃圾回收机制

    大致思路: 要进行垃圾回收,首先要判断一个对象是否活着,这就引出了两种方法…

     

    引用计数法和可达性分析法

     

    gc roots 类型

     

    引用类型

     

    两次标记过程

     

    垃圾回收算法

     

    内存分配策略

     

    触发垃圾回收

     

    垃圾回收器

     

    也会回收方法区

     

     

    回答:要进行垃圾回收,首先要判断对象是否存活,引出了两个方法:

     

    •  

    引用计数法

      • 思想:给对象设置引用计数器,没引用该对象一次,计数器就+1,引用失效时,计数器就-1,当任意时候引用计数器的值都为0时,则该对象可被回收
      • Java不适用原因:无法解决对象互相循环引用的问题
    •  

    可达性分析法

      • 以GC Roots为起点,从这些起点开始向下搜索,经过的路径称为引用链。若一个对象到GC Roots之间没有任何引用链,则该对象是不可达的。
      • 那么可作为GC Roots的对象有
        • 虚拟机栈(栈帧中的局部变量表)中引用的对象
        • 方法区中类静态属性引用的对象
        • 方法区中常量引用的对象
        • 本地方法栈中JNI(Native方法)引用的对象
    •  

    在可达性分析过程中,对象引用类型会对对象的生命周期产生影响,JAVA中有这几种类型的引用:

      • 强引用:只要该引用还有效,GC就不会回收
      • 软引用:内存空间足够时不进行回收,在内存溢出发生前进行回收、用SoftReference类实现
      • 弱引用:弱引用关联的对象只能存活到下一次Gc收集、用WeakReference类实现
      • 虚引用:无法通过虚引用获得对象实例,也不会对对象的生存时间产生影响、唯一目的:当该对象被Gc收集时,收到一个系统通知。用PhantomReference类实现
      •  

    一个对象真正不可用,要经历两次标记过程:

    • 首先进行可达性分析,筛选出与GC Roots没用引用链的对象,进行第一次标记
    • 第一次标记后,再进行一次筛选,筛选条件是是否有必要执行finalize()方法。若对象有没有重写finalize()方法,或者finalize()是否已被jvm调用过,则没必要执行,GC会回收该对象
    • 若有必要执行,则该对象会被放入F-Queue中,由jvm开启一个低优先级的线程去执行它(但不一定等待finalize执行完毕)。
    • Finalize()是对象最后一次自救的机会,若对象在finalize()中重新加入到引用链中,则它会被移出要回收的对象的集合。其他对象则会被第二次标记,进行回收

    JAVA中的垃圾回收算法有:

    • 标记-清除(Mark-Sweep)
      • 两个阶段:标记, 清除
      • 缺点:两个阶段的效率都不高;容易产生大量的内存碎片
    • 复制(Copying)
      • 把内存分成大小相同的两块,当一块的内存用完了,就把可用对象复制到另一块上,将使用过的一块一次性清理掉
      • 缺点:浪费了一半内存
    • 标记-整理(Mark-Compact)
      • 标记后,让所有存活的对象移到一端,然后直接清理掉端边界以外的内存
    • 分代收集
      • 把堆分为新生代和老年代
      • 新生代使用复制算法
      • 将新生代内存分为一块大的Eden区和两块小的Survivor;每次使用Eden和一个Survivor,回收时将Eden和Survivor存活的对象复制到另一个Survivor(HotSpot的比例Eden:Survivor = 8:1)
      • 老年代使用标记-清理或者标记-整理
      •  

    触发GC又涉及到了内存分配规则: (对象主要分配在Eden,若启动了本地线程分配缓冲,将优先在TLAB上分配)

    • 对象优先在Eden分配
      • 当Eden区没有足够的空间时就会发起一次Minor GC
    • 大对象直接进入老年代
      • 典型的大对象是很长的字符串和数组
    • 长期存活的对象进入老年代
      • 每个对象有年龄计数器,每经过一次GC,计数器值加一,当到达一定程度时(默认15),就会进入老年代
      • 年龄的阈值可通过参数 -XX:MaxTenuringThreshold设置
    • 对象年龄的判定
      • Survivor空间中相同年龄所有对象大小的总和大于Survivor空间的一半,年龄大于等于该年龄的对象就可直接进入老年代,无须等到MaxTenuringThreshold要求的年龄
    • 空间分配担保
      • 发生Minor GC前,jvm会检查老年代最大可用的连续空间是否大于新生代所有对象总空间,若大于,则Minor GC是安全的
      • 若不大于,jvm会查看HandlePromotionFailure是否允许担保失败,若不允许,则改为一次Full GC
      • 若允许担保失败,则检查老年代最大可用的连续空间是否大于历次晋升到老年代对象的平均大小,若大于,则尝试进行Minor GC;若小于,则要改为Full GC

    垃圾收集器:

    •  

    Serial(串行收集器)

      • 特性:单线程,stop the world,采用复制算法
      • 应用场景:jvm在Client模式下默认的新生代收集器
      • 优点:简单高效
    •  

    ParNew

      • 特点:是Serial的多线程版本,采用复制算法
      • 应用场景:在Server模式下常用的新生代收集器,可与CMS配合工作
    •  

    Parallel Scavenge

      • 特点:并行的多线程收集器,采用复制算法,吞吐量优先,有自适应调节策略
      • 应用场景:需要吞吐量大的时候
    •  

    SerialOld

      • 特点:Serial的老年代版本,单线程,使用标记-整理算法
    •  

    Parallel Old

      • Parallel Scavenge的老年代版本,多线程,标记-整理算法
    •  

    CMS

      • 特点:以最短回收停顿时间为目标,使用标记-清除算法
      • 过程:
        • 初始标记:stop the world 标记GC Roots能直接关联到的对象
        • 并发标记:进行GC Roots Tracing
        • 重新标记:stop the world;修正并发标记期间因用户程序继续运作而导致标记产生变动的 那一部分对象的标记记录
        • 并发清除:清除对象
      • 优点:并发收集,低停顿
      • 缺点:
        • 对CPU资源敏感
        • 无法处理浮动垃圾(并发清除 时,用户线程仍在运行,此时产生的垃圾为浮动垃圾)
        • 产生大量的空间碎片
    •  

    G1

      • 特点:面向服务端应用,将整个堆划分为大小相同的region。
        • 并行与并发
        • 分代收集
        • 空间整合:从整体看是基于“标记-整理”的,从局部(两个region之间)看是基于“复制”的。
        • 可预测的停顿:使用者可明确指定在一个长度为M毫秒的时间片段内,消耗在垃圾收集上的时间不得超过N毫秒。
      • 执行过程:
        • 初始标记:stop the world 标记GC Roots能直接关联到的对象
        • 并发标记:可达性分析
        • 最终标记:修正在并发标记期间因用户程序继续运作而导致标记产生变动的那一部分标记记录
        • 筛选回收:筛选回收阶段首先对各个Region的回收价值和成本进行排序,根据用户所期望的GC停顿时间来制定回收计划
    •  

    GC自适应调节策略 Parallel Scavenge收集器有一个参数-XX:+UseAdaptiveSizePolicy。当这个参数打开之后,就不需要手工指定新生代的大小、Eden与Survivor区的比例、晋升老年代对象年龄等细节参数了,虚拟机会根据当前系统的运行情况收集性能监控信息,动态调整这些参数以提供最合适的停顿时间或者最大的吞吐量,这种调节方式称为GC自适应的调节策略(GC Ergonomics)。

    •  

    (垃圾回收器部分重点讲CMS和G1)

    最后提一下也会回收方法区:

    • 永久代中主要回收两部分内容:废弃常量和无用的类
    • 废弃常量回收和对象的回收类似
    • 无用的类需满足3个条件
      • 该类的所有实例对象已被回收
      • 加载该类的ClassLoader已被回收
      • 该类的Class对象没有在任何地方被引用,无法在任何地方通过反射访问该类的方法

    上面的知识点在你多刷几遍书,脑中形成相应的知识网后能很全面的说出来。

    3、TCP和UDP的区别

    • TCP面向连接(如打电话要先拨号建立连接) UDP是无连接的,即发送数据之前不需要建立连接
    • TCP提供可靠的服务。也就是说,通过TCP连接传送的数据,无差错,不丢失,不重复,且按序到达;UDP尽最大努力交付,即不保证可靠交付
    • TCP面向字节流,实际上是TCP把数据看成一连串无结构的字节流;UDP是面向报文的
    • UDP没有拥塞控制,因此网络出现拥塞不会使源主机的发送速率降低(对实时应用很有用,如IP电话,实时视频会议等)
    • 每一条TCP连接只能是点到点的;UDP支持一对一,一对多,多对一和多对多的交互通信
    • TCP首部开销20字节;UDP的首部开销小,只有8个字节
    • TCP的逻辑通信信道是全双工的可靠信道,UDP则是不可靠信道

     

     

    4、项目是怎样预防sql注入的

    回答:用的是mybatis,sql语句中用#{},#{}表示一个占位符号,通过#{}可以实现preparedStatement向占位符中设置值,jdbc有个预编译的过程可以有效预防sql注入,尽量不用${},它是个拼接符,用来拼接sql字符串。

     

     

     

     

    1. MySQL存储引擎中的MyISAM和InnoDB区别

    在使用MySQL的过程中对MyISAM和InnoDB这两个概念存在了些疑问,到底两者引擎有何分别一直是存在我心中的疑问。为了解开这个谜题,搜寻了网络,找到了如下信息:

     

    MyISAM是MySQL的默认数据库引擎(5.5版之前),由早期的ISAM(Indexed Sequential Access Method:有索引的顺序访问方法)所改良。虽然性能极佳,但却有一个缺点:不支持事务处理(transaction)。不过,在这几年的发展下,MySQL也导入了InnoDB(另一种数据库引擎),以强化参考完整性与并发违规处理机制,后来就逐渐取代MyISAM。

     

    InnoDB,是MySQL的数据库引擎之一,为MySQL AB发布binary的标准之一。InnoDB由Innobase Oy公司所开发,2006年五月时由甲骨文公司并购。与传统的ISAM与MyISAM相比,InnoDB的最大特色就是支持了ACID兼容的事务(Transaction)功能,类似于PostgreSQL。目前InnoDB采用双轨制授权,一是GPL授权,另一是专有软件授权。

     

    MyISAM与InnoDB的区别是什么?

     

    存储结构

     

    MyISAM:每个MyISAM在磁盘上存储成三个文件。第一个文件的名字以表的名字开始,扩展名指出文件类型。.frm文件存储表定义。数据文件的扩展名为.MYD (MYData)。索引文件的扩展名是.MYI (MYIndex)。

    InnoDB:所有的表都保存在同一个数据文件中(也可能是多个文件,或者是独立的表空间文件),InnoDB表的大小只受限于操作系统文件的大小,一般为2GB。

     

    存储空间

     

    MyISAM:可被压缩,存储空间较小。支持三种不同的存储格式:静态表(默认,但是注意数据末尾不能有空格,会被去掉)、动态表、压缩表。

    InnoDB:需要更多的内存和存储,它会在主内存中建立其专用的缓冲池用于高速缓冲数据和索引。

     

    可移植性、备份及恢复

     

    MyISAM:数据是以文件的形式存储,所以在跨平台的数据转移中会很方便。在备份和恢复时可单独针对某个表进行操作。

    InnoDB:免费的方案可以是拷贝数据文件、备份 binlog,或者用 mysqldump,在数据量达到几十G的时候就相对痛苦了。

     

    事务支持

     

    MyISAM:强调的是性能,每次查询具有原子性,其执行数度比InnoDB类型更快,但是不提供事务支持。

    InnoDB:提供事务支持事务,外部键等高级数据库功能。 具有事务(commit)、回滚(rollback)和崩溃修复能力(crash recovery capabilities)的事务安全(transaction-safe (ACID compliant))型表。

     

    AUTO_INCREMENT

     

    MyISAM:可以和其他字段一起建立联合索引。引擎的自动增长列必须是索引,如果是组合索引,自动增长可以不是第一列,他可以根据前面几列进行排序后递增。

    InnoDB:InnoDB中必须包含只有该字段的索引。引擎的自动增长列必须是索引,如果是组合索引也必须是组合索引的第一列。

     

    表锁差异

     

    MyISAM:只支持表级锁,用户在操作myisam表时,select,update,delete,insert语句都会给表自动加锁,如果加锁以后的表满足insert并发的情况下,可以在表的尾部插入新的数据。

    InnoDB:支持事务和行级锁,是innodb的最大特色。行锁大幅度提高了多用户并发操作的新能。但是InnoDB的行锁,只是在WHERE的主键是有效的,非主键的WHERE都会锁全表的。

     

    全文索引

     

    MyISAM:支持 FULLTEXT类型的全文索引

    InnoDB:不支持FULLTEXT类型的全文索引,但是innodb可以使用sphinx插件支持全文索引,并且效果更好。

     

    表主键

     

    MyISAM:允许没有任何索引和主键的表存在,索引都是保存行的地址。

    InnoDB:如果没有设定主键或者非空唯一索引,就会自动生成一个6字节的主键(用户不可见),数据是主索引的一部分,附加索引保存的是主索引的值。

     

    表的具体行数

     

    MyISAM:保存有表的总行数,如果select count(*) from table;会直接取出出该值。

    InnoDB:没有保存表的总行数,如果使用select count(*) from table;就会遍历整个表,消耗相当大,但是在加了wehre条件后,myisam和innodb处理的方式都一样。

     

    CURD操作

     

    MyISAM:如果执行大量的SELECT,MyISAM是更好的选择。

    InnoDB:如果你的数据执行大量的INSERT或UPDATE,出于性能方面的考虑,应该使用InnoDB表。DELETE 从性能上InnoDB更优,但DELETE FROM table时,InnoDB不会重新建立表,而是一行一行的删除,在innodb上如果要清空保存有大量数据的表,最好使用truncate table这个命令。

     

    外键

     

    MyISAM:不支持

    InnoDB:支持

    通过上述的分析,基本上可以考虑使用InnoDB来替代MyISAM引擎了,原因是InnoDB自身很多良好的特点,比如事务支持、存储 过程、视图、行级锁定等等,在并发很多的情况下,相信InnoDB的表现肯定要比MyISAM强很多。另外,任何一种表都不是万能的,只用恰当的针对业务类型来选择合适的表类型,才能最大的发挥MySQL的性能优势。如果不是很复杂的Web应用,非关键应用,还是可以继续考虑MyISAM的,这个具体情况可以自己斟酌。

     

     

    在MySQL数据库中,常用的引擎主要就是2个:Innodb和MyIASM。

     

     

     

    其他的解释:   首先:

     

    (1)简单介绍这两种引擎,以及该如何去选择。

    (2)这两种引擎所使用的数据结构是什么。

     

     

    a.Innodb引擎,Innodb引擎提供了对数据库ACID事务的支持。并且还提供了行级锁和外键的约束。它的设计的目标就是处理大数据容量的数据库系统。它本身实际上是基于Mysql后台的完整的系统。Mysql运行的时候,Innodb会在内存中建立缓冲池,用于缓冲数据和索引。但是,该引擎是不支持全文搜索的。同时,启动也比较的慢,它是不会保存表的行数的。当进行Select count(*) from table指令的时候,需要进行扫描全表。所以当需要使用数据库的事务时,该引擎就是首选。由于锁的粒度小,写操作是不会锁定全表的。所以在并发度较高的场景下使用会提升效率的。

     

    b.MyIASM引擎,它是MySql的默认引擎,但不提供事务的支持,也不支持行级锁和外键。因此当执行Insert插入和Update更新语句时,即执行写操作的时候需要锁定这个表。所以会导致效率会降低。不过和Innodb不同的是,MyIASM引擎是保存了表的行数,于是当进行Select count(*) from table语句时,可以直接的读取已经保存的值而不需要进行扫描全表。所以,如果表的读操作远远多于写操作时,并且不需要事务的支持的。可以将MyIASM作为数据库引擎的首先。

     

    补充2点:

     

    c.大容量的数据集时趋向于选择Innodb。因为它支持事务处理和故障的恢复。Innodb可以利用数据日志来进行数据的恢复。主键的查询在Innodb也是比较快的。

     

    d.大批量的插入语句时(这里是INSERT语句)在MyIASM引擎中执行的比较的快,但是UPDATE语句在Innodb下执行的会比较的快,尤其是在并发量大的时候。

     

    两种引擎所使用的索引的数据结构是什么?

     

    答案:都是B+树!

     

    MyIASM引擎,B+树的数据结构中存储的内容实际上是实际数据的地址值。也就是说它的索引和实际数据是分开的,只不过使用索引指向了实际数据。这种索引的模式被称为非聚集索引。

     

    Innodb引擎的索引的数据结构也是B+树,只不过数据结构中存储的都是实际的数据,这种索引有被称为聚集索引。

     

     

     

    6、B树与B+树简明扼要的区别

    看了很多讲B树和B+树的文章,大多都是围绕各自的特性讲的,第一,树中每个结点最多含有m个孩子(m>=2);第二,……我也是从这些文章里弄懂了各种树的联系与区别,要真写,我可能还不如人家写得好。所以就在这里简明扼要的用几张图记录一下主要区别吧。 

     

      为了便于说明,我们先定义一条数据记录为一个二元组[key,data],key为记录的键值,key唯一;data为数据记录除key外的数据。

     

     

    B树

     

      每个节点都存储key和data,所有节点组成这棵树,并且叶子节点指针为null。

     

      

     

    B+树

     

      只有叶子节点存储data,叶子节点包含了这棵树的所有键值,叶子节点不存储指针。

     

      

     

      后来,在B+树上增加了顺序访问指针,也就是每个叶子节点增加一个指向相邻叶子节点的指针,这样一棵树成了数据库系统实现索引的首选数据结构。 

     

      原因有很多,最主要的是这棵树矮胖,呵呵。一般来说,索引很大,往往以索引文件的形式存储的磁盘上,索引查找时产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的时间复杂度。树高度越小,I/O次数越少。 

     

      那为什么是B+树而不是B树呢,因为它内节点不存储data,这样一个节点就可以存储更多的key。

     

     

     

      在MySQL中,最常用的两个存储引擎是MyISAM和InnoDB,它们对索引的实现方式是不同的。

     

     

     

    MyISAM 

     

      data存的是数据地址。索引是索引,数据是数据。

     

    InnoDB

     

      data存的是数据本身。索引也是数据。

     

      

     

      了解了数据结构再看索引,一切都不费解了,只是顺着逻辑推而已。

     

     

     

    1. 解决哈希冲突的三种方法(拉链法、开放地址法、再散列法)

    上篇博客我们说到了,什么是哈希冲突,其实就是再采用哈希函数对输入域进行映射到哈希表的时候,因为哈希表的位桶的数目远小于输入域的关键字的个数,所以,对于输入域的关键字来说,很可能会产生这样一种情况,也就是,一个关键字会映射到同一个位桶中的情况,这种情况就就叫做哈希冲突,解决哈希冲突的有三种方案,一种叫做拉链法(也叫作链接法、链地址法,一个意思),另外三种分别为开发地址法和再散列法。

     

    (1)拉链法

     

    上篇博文我们举的例子,HashMap,HashSet其实都是采用的拉链法来解决哈希冲突的,就是在每个位桶实现的时候,我们采用链表(jdk1.8之后采用链表+红黑树)的数据结构来去存取发生哈希冲突的输入域的关键字(也就是被哈希函数映射到同一个位桶上的关键字)。首先来看使用拉链法解决哈希冲突的几个操作:

     

    ①插入操作:在发生哈希冲突的时候,我们输入域的关键字去映射到位桶(实际上是实现位桶的这个数据结构,链表或者红黑树)中去的时候,我们先检查带插入元素x是否出现在表中,很明显,这个查找所用的次数不会超过装载因子(n/m:n为输入域的关键字个数,m为位桶的数目),它是个常数,所以插入操作的最坏时间复杂度为O(1)的。

     

    ②查询操作:和①一样,在发生哈希冲突的时候,我们去检索的时间复杂度不会超过装载因子,也就是检索数据的时间复杂度也是O(1)的

     

    ③删除操作:如果在拉链法中我们想要使用链表这种数据结构来实现位桶,那么这个链表一定是双向链表,因为在删除一个元素x的时候,需要更改x的前驱元素的next指针的属性,把x从链表中删除。这个操作的时间复杂度也是O(1)的。

     

     

     

    拉链法的优点

     

    与开放定址法相比,拉链法有如下几个优点:

     

    ①拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;

     

    ②由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;

     

    ③开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;

     

    ④在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

     

     

     

    拉链法的缺点

     

    指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。

     

    使用例子:

     

    HashMap

     

    (2)开发地址法

     

    开放地址法有个非常关键的特征,就是所有输入的元素全部存放在哈希表里,也就是说,位桶的实现是不需要任何的链表来实现的,换句话说,也就是这个哈希表的装载因子不会超过1。它的实现是在插入一个元素的时候,先通过哈希函数进行判断,若是发生哈希冲突,就以当前地址为基准,根据再寻址的方法(探查序列),去寻找下一个地址,若发生冲突再去寻找,直至找到一个为空的地址为止。所以这种方法又称为再散列法。

     

    有几种常用的探查序列的方法:

     

    ①线性探查

     

    dii=1,2,3,…,m-1;这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

     

    (使用例子:ThreadLocal里面的ThreadLocalMap)

     

    ②二次探查

     

    di=12,-12,22,-22,…,k2,-k2    ( k<=m/2 );这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。

     

    ③ 伪随机探测

     

    di=伪随机数序列;具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),生成一个位随机序列,并给定一个随机数做起点,每次去加上这个伪随机数++就可以了。

     

    (3)再散列法

     

    再散列法其实很简单,就是再使用哈希函数去散列一个输入的时候,输出是同一个位置就再次散列,直至不发生冲突位置

     

    缺点:每次冲突都要重新散列,计算时间增加。

     

     

    7、forward(转发)和redirect(重定向)有什么区别

     

    forward和redirect是什么?

    是servlet种的两种主要的跳转方式。forward又叫转发,redirect叫做重定向。

     

    forward(转发):

    1.是服务器内部的重定向,服务器直接访问目标地址的 url网址,把里面的东西读取出来,但是客户端并不知道,因此用forward的话,客户端浏览器的网址是不会发生变化的。

    2.关于request: 由于在整个定向的过程中用的是同一个request,因此forward会将request的信息带到被重定向的jsp或者servlet中使用。

     

    redirect(重定向):

    1.是客户端的重定向,是完全的跳转。即服务器返回的一个url给客户端浏览器,然后客户端浏览器会重新发送一次请求,到新的url里面,因此浏览器中显示的url网址会发生变化。

    2.因为这种方式比forward多了一次网络请求,因此效率会低于forward。

     

     

     

    8、set、list、map

    List,Set,Map是否继承自Collection接口? 

    答:List,Set是,Map不是。 Collection是最基本的集合接口,一个Collection代表一组Object,即Collection的元素。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java JDK不能提供直接继承自Collection的类,Java JDK提供的类都是继承自Collection的"子接口",如:List和Set。 

    注意:Map没有继承Collection接口,Map提供key到value的映射。一个Map中不能包含相同key,每个key只能映射一个value。Map接口提供3种集合的视图,Map的内容可以被当做一组key集合,一组value集合,或者一组key-value映射。 

    List按对象进入的顺序保存对象,不做排序或编辑操作。Set对每个对象只接受一次,并使用自己内部的排序方法(通常,你只关心某个元素是否属于Set,而不关心它的顺序--否则应该使用List)。Map同样对每个元素保存一份,但这是基于"键"的,Map也有内置的排序,因而不关心元素添加的顺序。如果添加元素的顺序对你很重要,应该使用 LinkedHashSet或者LinkedHashMap.

     

    详细介绍: 

    List特点:元素有放入顺序,元素可重复 

    Map特点:元素按键值对存储,无放入顺序 

    Set特点:元素无放入顺序,元素不可重复(注意:元素虽然无放入顺序,但是元素在set中的位置是有该元素的HashCode决定的,其位置其实是固定的) 

    List接口有三个实现类:LinkedList,ArrayList,Vector 

    LinkedList:底层基于链表实现,链表内存是散乱的,每一个元素存储本身内存地址的同时还存储下一个元素的地址。链表增删快,查找慢 

    ArrayList和Vector的区别:ArrayList是非线程安全的,效率高;Vector是基于线程安全的,效率低 

    Set接口有两个实现类:HashSet(底层由HashMap实现),LinkedHashSet 

    SortedSet接口有一个实现类:TreeSet(底层由平衡二叉树实现) 

    Query接口有一个实现类:LinkList 

    Map接口有三个实现类:HashMap,HashTable,LinkeHashMap 

      HashMap非线程安全,高效,支持null;HashTable线程安全,低效,不支持null 

    SortedMap有一个实现类:TreeMap 

    其实最主要的是,list是用来处理序列的,而set是用来处理集的。Map是知道的,存储的是键值对 

    set 一般无序不重复.map kv 结构 list 有序 。

     

     

    List的功能方法

     

      实际上有两种List: 一种是基本的ArrayList,其优点在于随机访问元素,另一种是更强大的LinkedList,它并不是为快速随机访问设计的,而是具有一套更通用的方法。

     

    List : 次序是List最重要的特点:它保证维护元素特定的顺序。List为Collection添加了许多方法,使得能够向List中间插入与移除元素(这只推荐LinkedList使用。)一个List可以生成ListIterator,使用它可以从两个方向遍历List,也可以从List中间插入和移除元素。

     

    ArrayList : 由数组实现的List。允许对元素进行快速随机访问,但是向List中间插入与移除元素的速度很慢。ListIterator只应该用来由后向前遍历ArrayList,而不是用来插入和移除元素。因为那比LinkedList开销要大很多。

     

    LinkedList : 对顺序访问进行了优化,向List中间插入与删除的开销并不大。随机访问则相对较慢。(使用ArrayList代替。)还具有下列方法:addFirst(), addLast(), getFirst(), getLast(), removeFirst() 和 removeLast(), 这些方法 (没有在任何接口或基类中定义过)使得LinkedList可以当作堆栈、队列和双向队列使用。

     

    Set的功能方法

     

    Set具有与Collection完全一样的接口,因此没有任何额外的功能,不像前面有两个不同的List。实际上Set就是Collection,只是行为不同。(这是继承与多态思想的典型应用:表现不同的行为。)Set不保存重复的元素(至于如何判断元素相同则较为负责)

     

    Set : 存入Set的每个元素都必须是唯一的,因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set与Collection有完全一样的接口。Set接口不保证维护元素的次序。

     

    HashSet : 为快速查找设计的Set。存入HashSet的对象必须定义hashCode()。

     

    TreeSet : 保存次序的Set, 底层为树结构。使用它可以从Set中提取有序的序列。

     

    LinkedHashSet : 具有HashSet的查询速度,且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时,结果会按元素插入的次序显示。

     

    Map的功能方法

     

      方法put(Object key, Object value)添加一个“值”(想要得东西)和与“值”相关联的“键”(key)(使用它来查找)。方法get(Object key)返回与给定“键”相关联的“值”。可以用containsKey()和containsValue()测试Map中是否包含某个“键”或“值”。标准的Java类库中包含了几种不同的Map:HashMap, TreeMap, LinkedHashMap, WeakHashMap, IdentityHashMap。它们都有同样的基本接口Map,但是行为、效率、排序策略、保存对象的生命周期和判定“键”等价的策略等各不相同。

     

      执行效率是Map的一个大问题。看看get()要做哪些事,就会明白为什么在ArrayList中搜索“键”是相当慢的。而这正是HashMap提高速度的地方。HashMap使用了特殊的值,称为“散列码”(hash code),来取代对键的缓慢搜索。“散列码”是“相对唯一”用以代表对象的int值,它是通过将该对象的某些信息进行转换而生成的。所有Java对象都能产生散列码,因为hashCode()是定义在基类Object中的方法。

     

    HashMap就是使用对象的hashCode()进行快速查询的。此方法能够显著提高性能。

     

    Map : 维护“键值对”的关联性,使你可以通过“键”查找“值”

     

    HashMap : Map基于散列表的实现。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量capacity和负载因子load factor,以调整容器的性能。

     

    LinkedHashMap : 类似于HashMap,但是迭代遍历它时,取得“键值对”的顺序是其插入次序,或者是最近最少使用(LRU)的次序。只比HashMap慢一点。而在迭代访问时发而更快,因为它使用链表维护内部次序。

     

    TreeMap : 基于红黑树数据结构的实现。查看“键”或“键值对”时,它们会被排序(次序由Comparabel或Comparator决定)。TreeMap的特点在于,你得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map,它可以返回一个子树。

     

    WeakHashMao : 弱键(weak key)Map,Map中使用的对象也被允许释放: 这是为解决特殊问题设计的。如果没有map之外的引用指向某个“键”,则此“键”可以被垃圾收集器回收。

     

    IdentifyHashMap : 使用==代替equals()对“键”作比较的hash map。专为解决特殊问题而设计。

     

     

     

    1. HashMap、Hashtable、ConcurrentHashMap的原理与区别

    如果你去面试,面试官不问你这个问题,你来找我^_^

    下面直接来干货,先说这三个Map的区别:

    HashTable

    • 底层数组+链表实现,无论key还是value都不能为null,线程安全,实现线程安全的方式是在修改数据时锁住整个HashTable,效率低,ConcurrentHashMap做了相关优化
    • 初始size为11,扩容:newsize = olesize*2+1
    • 计算index的方法:index = (hash & 0x7FFFFFFF) % tab.length

    HashMap

    • 底层数组+链表实现,可以存储null键和null值,线程不安全
    • 初始size为16,扩容:newsize = oldsize*2,size一定为2的n次幂
    • 扩容针对整个Map,每次扩容时,原来数组中的元素依次重新计算存放位置,并重新插入
    • 插入元素后才判断该不该扩容,有可能无效扩容(插入后如果扩容,如果没有再次插入,就会产生无效扩容)
    • 当Map中元素总数超过Entry数组的75%,触发扩容操作,为了减少链表长度,元素分配更均匀
    • 计算index方法:index = hash & (tab.length – 1)

     

    HashMap的初始值还要考虑加载因子:

    •  哈希冲突:若干Key的哈希值按数组大小取模后,如果落在同一个数组下标上,将组成一条Entry链,对Key的查找需要遍历Entry链上的每个元素执行equals()比较。
    • 加载因子:为了降低哈希冲突的概率,默认当HashMap中的键值对达到数组大小的75%时,即会触发扩容。因此,如果预估容量是100,即需要设定100/0.75=134的数组大小。
    • 空间换时间:如果希望加快Key查找的时间,还可以进一步降低加载因子,加大初始大小,以降低哈希冲突的概率。

    HashMap和Hashtable都是用hash算法来决定其元素的存储,因此HashMap和Hashtable的hash表包含如下属性:

    • 容量(capacity):hash表中桶的数量
    • 初始化容量(initial capacity):创建hash表时桶的数量,HashMap允许在构造器中指定初始化容量
    • 尺寸(size):当前hash表中记录的数量
    • 负载因子(load factor):负载因子等于“size/capacity”。负载因子为0,表示空的hash表,0.5表示半满的散列表,依此类推。轻负载的散列表具有冲突少、适宜插入与查询的特点(但是使用Iterator迭代元素时比较慢)

    除此之外,hash表里还有一个“负载极限”,“负载极限”是一个0~1的数值,“负载极限”决定了hash表的最大填满程度。当hash表中的负载因子达到指定的“负载极限”时,hash表会自动成倍地增加容量(桶的数量),并将原有的对象重新分配,放入新的桶内,这称为rehashing。

    HashMap和Hashtable的构造器允许指定一个负载极限,HashMap和Hashtable默认的“负载极限”为0.75,这表明当该hash表的3/4已经被填满时,hash表会发生rehashing。

    “负载极限”的默认值(0.75)是时间和空间成本上的一种折中:

    • 较高的“负载极限”可以降低hash表所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的操作(HashMap的get()与put()方法都要用到查询)
    • 较低的“负载极限”会提高查询数据的性能,但会增加hash表所占用的内存开销

    程序猿可以根据实际情况来调整“负载极限”值。

    ConcurrentHashMap

    • 底层采用分段的数组+链表实现,线程安全
    • 通过把整个Map分为N个Segment,可以提供相同的线程安全,但是效率提升N倍,默认提升16倍。(读操作不加锁,由于HashEntry的value变量是 volatile的,也能保证读取到最新的值。)
    • Hashtable的synchronized是针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术
    • 有些方法需要跨段,比如size()和containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁
    • 扩容:段内扩容(段内元素超过该段对应Entry数组长度的75%触发扩容,不会对整个Map进行扩容),插入前检测需不需要扩容,有效避免无效扩容

     

    Hashtable和HashMap都实现了Map接口,但是Hashtable的实现是基于Dictionary抽象类的。Java5提供了ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好。

    HashMap基于哈希思想,实现对数据的读写。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,然后找到bucket位置来存储值对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞时,对象将会储存在链表的下一个节点中。HashMap在每个链表节点中储存键值对对象。当两个不同的键对象的hashcode相同时,它们会储存在同一个bucket位置的链表中,可通过键对象的equals()方法来找到键值对。如果链表大小超过阈值(TREEIFY_THRESHOLD,8),链表就会被改造为树形结构。

    在HashMap中,null可以作为键,这样的键只有一个,但可以有一个或多个键所对应的值为null。当get()方法返回null值时,即可以表示HashMap中没有该key,也可以表示该key所对应的value为null。因此,在HashMap中不能由get()方法来判断HashMap中是否存在某个key,应该用containsKey()方法来判断。而在Hashtable中,无论是key还是value都不能为null。

    Hashtable是线程安全的,它的方法是同步的,可以直接用在多线程环境中。而HashMap则不是线程安全的,在多线程环境中,需要手动实现同步机制。

    Hashtable与HashMap另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException,但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。

    先看一下简单的类图:

     

      

    从类图中可以看出来在存储结构中ConcurrentHashMap比HashMap多出了一个类Segment,而Segment是一个可重入锁。

    ConcurrentHashMap是使用了锁分段技术来保证线程安全的。

    锁分段技术:首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。 

    ConcurrentHashMap提供了与Hashtable和SynchronizedMap不同的锁机制。Hashtable中采用的锁机制是一次锁住整个hash表,从而在同一时刻只能由一个线程对其进行操作;而ConcurrentHashMap中则是一次锁住一个桶。

    ConcurrentHashMap默认将hash表分为16个桶,诸如get、put、remove等常用操作只锁住当前需要用到的桶。这样,原来只能一个线程进入,现在却能同时有16个写线程执行,并发性能的提升是显而易见的。

     

    展开全文
  • 通信 之 无线信道衰落

    万次阅读 2018-03-15 17:10:09
    这两天捋了下信道衰落方面知识,汇总如下。1信道定义参考http://blog.csdn.net/a493823882/article/details/78264608主要:移动无线信道是随参信道,传输特性是变化的。所以要考虑①对信号的衰耗随时间随机变化;②...

    这两天捋了下信道衰落方面知识,汇总如下。

    1信道定义

    参考http://blog.csdn.net/a493823882/article/details/78264608

    主要:移动无线信道是随参信道,传输特性是变化的。所以要考虑①对信号的衰耗随时间随机变化;②信号传输的时延随时间随机变化③多径传播

    2无线信道衰落

    定义参考http://blog.csdn.net/a493823882/article/details/78264608

    分类参考http://blog.csdn.net/u010237785/article/details/53483070,如下图:

    (说明:尺度是相对于波长来讲的。大尺度是指距离远远大于波长,是宏观意义上的衰落;小尺度是几倍波长,短距离、短时间,研究的是微观意义上的衰落)

    计算公式参考http://blog.csdn.net/InvertibleMatrix/article/details/77308233

    2.1路径损耗

    电波在空间传播所产生的损耗,是由发射功率辐射扩散及信道的传播特性造成的,反映宏观范围内接收信号功率均值的变化。理论上认为,对于相同的收发距离,路径损耗也相同。但实践中往往发现,相同收发距离的不同接收点上的接收功率却存在较大变化,甚至同一接收点上的接收功率在不同时间点上也产生较大波动。

    不考虑任何遮挡,自由空间传播模型为

    Pr(d)=PtGtGrλ2(4π)2d2

    从上式可以看出,波长越长,衰减越小,接收功率Pr越大;距离越长,衰减越大,Pr越小。Pr的衰减就是由路损带来的。

    路径损耗公式:(参考http://www.eefocus.com/yuyanqiang1982/blog/12-05/247832_701b8.html)

      PL=37 dB + 20log(fMHz) + 20log(d)(不同模型公式不同)

      其中,d为距离或范围,单位为英里,1英里约等于1610米;f为发射信号频率。得到了给定天线组的路径损耗和发射功率之后,就可以用下式确定所需要的接收器灵敏度:

      Pr=Pt–PL

      假设路径损耗为90 dB,发射功率为10dBm (10 mW),则需要的接收器灵敏度为:

      Pr=10–90=–80dBm

    2.2阴影效应

    在无线通信系统中,移动台在运动的情况下,由于大型建筑物和其他物体对电波的传输路径的阻挡而在传播接收区域上形成半盲区,从而形成电磁场阴影,这种随移动台位置的不断变化而引起的接收点场强中值的起伏变化叫做阴影效应。

    阴影衰落一般服从对数正态分布(注:若x服从对数正态,则lnx服从正态分布。),概率密度函数为

    p(x)=12πσe(lnxμ)22σ2

    2.3多径效应

    指电磁波经不同路径传播后,各分量场到达接收端时间不同,按各自相位相互叠加而造成干扰,使得原来的信号失真,或者产生错误。

    多径效应产生时延扩展(信号最快和最慢到达接收端的时差),导致多路信号叠加后产生多径衰落,对该衰落建的模有比如瑞利型衰落,指接收端信号的振幅V(t)的一维分布服从瑞利分布(即在任意时刻ti,V(ti)都是一个服从瑞利分布的随机值),可以参考http://blog.csdn.net/a493823882/article/details/78264608。从频谱上看,多径效应使单一谱线变成了窄带频谱,即多径传播引起了频率弥散。

    至于频率选择性衰落和平坦衰落,若信号带宽(如LTE的子载波带宽15kHz)小于信道的相干带宽,则在信号自身的频带内经历的信道基本一样,则为平坦衰落;反之,信号在自身的频带内不同频率经历的信道差别很大,导致不同频率的衰落不同,称之为频率选择性衰落。(关于信道相干带宽与时延扩展成反比,具体含义参考http://blog.csdn.net/JonTargaryen/article/details/68943588)

    由于多径效应的影响,信号到达时间会产生变化。由于到达时间的变化,同一载波内的符号之间会相互干扰,形成符号间干扰(ISI)。为了消除符号问干扰(ISl),应该在符号间插入保护间隔。

    2.4多普勒效应

    定义参考

    https://baike.baidu.com/item/%E5%A4%9A%E6%99%AE%E5%8B%92%E6%95%88%E5%BA%94/115710?fr=aladdin

    简单理解,当观察者走近波源时观察到的波源频率为(c+v)/λ,反之则观察到的波源频率为(c-v)/λ。

    公式:
    观察者 (Observer) 和发射源 (Source) 的频率关系为:
    为观察到的频率;
    为发射源于该介质中的原始发射频率;
      
    为波在该介质中的行进速度;
      
    为观察者移动速度,若接近发射源则前方运算符号为 + 号, 反之则为 - 号;
      
    为发射源移动速度,若接近观察者则前方运算符号为 - 号,反之则为 + 号。

    多普勒效应带来了多普勒扩展(即多普勒频移),信道的相干时间与最大多普勒频移成反比,若发射信号的符号周期小于相干时间,那么认为接收信号经历的是慢衰落(时间非选择性衰落),否则认为接收信号经历的是快衰落(时间选择性衰落)。(相干时间是指信道保持不变的时间,具体含义参考http://blog.csdn.net/JonTargaryen/article/details/68943588)

    由于多普勒效应的影响,信号其中心频率会产生偏移。由于中心频率的频移,信号会对其他载波造成干扰,形成载波间干扰(ICI)。在OFDM中,为了消除ICI,通常保护间隔是由循环前缀CP来充当(这样既能消除ICI,又能消除ISI)。

    展开全文
  • 为什么Wi-Fi用的最多是1,6,11 信道

    万次阅读 2017-11-26 15:27:22
    目前主流的无线WIFI网络设备不管是802.11b/g还是802.11b/g/n 一般都支持13个信道。它们的中心频率虽然不同,但是因为都占据一定的频率范围,所以会有一些相互重叠的情况。下面是13个信道的频率范围列表。了解这13个...
  • 一、信道划分介质访问控制 (一)传输数据使用的两种链路 点对点链路:两个相邻节点通过一个链路相连,没有第三者。...信道划分介质访问控制:将使用介质的每个设备与来自同一信道上的其他设备的通信隔离开,把时域
  • 数据传输允许数据两个方向上传输,但是,任何时刻只能由其中的一方发送数据,另一方接收数据。因此半双工模式既可以使用一条数据线,也可以使用两条数据线。它实际上是一种切换方向的单工通信,就和对讲机(步话...
  • 论坛上不少朋友很困惑,为什么小极的自动信道选择选到的信道只会1、6、11这三个信道呢?WiFi不是一共有10几个信道吗?其他信道岂不是浪费了?这个问题是个非常典型的问题,问100个人,几乎100个人不知道答案的。...
  • 信道概念

    2019-12-10 16:40:38
    其动态信号x(t)是描述信号不同时刻取值的函数。 时域(时间域)——自变量是时间,即横轴是时间,纵轴是信号的变化。其动态信号x(t)是描述信号不同时刻取值的函数。 两者之间可以互相转化。时域函数通过傅立叶...
  • 需要解决的一个问题是,如何让多个用户能够合理而方便的使用共享信道物理媒介上不产生信号冲突。技术上有两种方案: 静态信道划分 物理上使用频分复用、时分复用、码分复用等,但这中方式的信道利用率低且...
  • OFDM系统中的信道估计基础知识

    万次阅读 多人点赞 2020-10-04 15:18:25
    参考文章: 信道估计(百度百科) OFDM学习笔记(四)...举一个简单的栗子来说,假如发送端发送了一个正弦信号6sin(2t),然后发送的这个正弦信号无线信道中进行传输,由于信道的影响,接收端接到的信号变成了3sin
  • LTE下行物理层传输机制(3)-PHICH信道

    万次阅读 多人点赞 2016-06-02 22:59:26
    同一个终端在同一个子帧中分配的上行RB是连续的,且每个终端之间分配的上行RB并不会重叠,因此对于同个子帧中不同的终端来说,该参数不相同。下图是一个简单的示意图,用于帮助理解。 (4) N_PHICH_SF 参数:该参数...
  • 文章目录1.局域网的数据链路层 ...局域网上的主机可共享连接局域网上的各种硬件和软件资源。 便于系统的扩展和逐渐地演变,各设备的位置可灵活调整和改变。 提高了系统的可靠性、可用性和残存性。 ...
  • 为什么小极的自动信道选择选到的信道只会1、6、11这三个信道呢?WiFi不是一共有10几个信道吗?其他信道岂不是浪费了? 这个问题是个非常典型的问题,问100个人,几乎100个人不知道答案的。为了回答这个问题,我...
  • 数字信号:一个信号某一段时间内信号强度保持某个常量值,然后在下一时段又变化为另一个常量值。 周期信号:周而复始不断重复的信号。 正弦波是最基本的模拟周期信号,可以用3个参数表示:幅度、频率...
  • 信道分析

    万次阅读 2018-10-12 10:40:19
    信道分析技术简介 是对安全芯片的侧信道分析(side channel ... 根据目前报道的文献资料,如未对侧信道攻击进行防御设计,许多算法都可短期内(几分钟到数天)被破解。 侧信道分析攻击方式成为破解密码芯...
  • 信道相关基础知识

    2021-04-14 15:33:13
    信道相关基础知识1、相关领域基础知识1.1、似然函数1.2、先验概率和后验概率1.3、卷积2、信道相关基本概念2.1、对称信道2.2、常见错误的基本概念2.2.1、码元和码字2.2.2、错误类型2.2.3、二元码 1、相关领域基础知识...
  • 信道划分介质访问控制 传输数据的时候使用的两种链路 点对点式链路 两个相邻的节点通过一个...定义:将使用介质的每个设备与来自同一信道上的其他设备的通信隔离开来,将时域和频域资源合理地分配给网络上的设备 多路复
  • 论坛上不少朋友很困惑,为什么小极的自动信道选择选到的信道只会1、6、11这三个信道呢?WiFi不是一共有10几个信道吗?其他信道岂不是浪费了? 这个问题是个非常典型的问题,问100个人,几乎100个人不知道答案的...
  • rabbitmq面试题

    2019-09-05 23:08:46
    分布式系统下具备异步,削峰,负载均衡等一系列高级功能; 拥有持久化的机制,进程消息,队列中的信息也可以保存下来。 实现消费者和生产者之间的解耦。 对于高并发场景下,利用消息队列可以使得同步访问变为串...
  • 无线 WIFI 的13个信道频率范围

    千次阅读 2019-10-11 17:42:20
    目前主流的无线WIFI网络设备不管是802.11b/g还是802.11b/g/n 一般都支持13个信道。它们的中心频率虽然不同,但是因为都占据一定的频率范围,所以会有一些相互重叠的情况。下面是13个信道的频率范围列表。了解这13个...
  • 为什么小极的自动信道选择选到的信道只会1、6、11这三个信道呢?WiFi不是一共有10几个信道吗?其他信道岂不是浪费了? 这个问题是个非常典型的问题,问100个人,几乎100个人不知道答案的。为了回答这个问题,我...
  • 计算机网络技术期末个人总结

    千次阅读 多人点赞 2019-04-26 14:56:43
    码元传输的速率越高,或信号传输的距离越远,在信道的输出端的波形的失真就越严重。 奈氏(Nyquist) 准则 • 理想低通(无噪)信道的最高码元传输率 速率 = 2W Baud • W是理想低通信道的带宽,单位为赫兹Hz...
  • 802.11ac 速率 + 信道 + 国家码信道

    千次阅读 2020-05-15 20:46:32
    转载 ... 3.1 802.11ac的信道绑定 802.11n协议中,可以将两个相邻的20MHz子信道绑定一起作为40...
  • 多径信道理论的直观感受与MATLAB仿真 -...1.多径信道下的衰落仿真 2. 信道的时变性 3.结论 4.仿真代码 争取后面有时间了,能够补上多径信道模型的仿真, 就不用每次都是高斯信道仿真了。!!!∑(゚Д゚ノ)ノ ...
  • C++ 面试题大全

    千次阅读 多人点赞 2017-05-31 09:42:54
    结构和联合都是由多个不同的数据类型成员组成, 但任何同一时刻,联合中只存放了一个被选中的成员(所有成员共用一块地址空间), 而结构的所有成员都存在(不同成员的存放地址不同)。 (2). 对于联合的不同成员...
  • 如果发送数据之前,我们能够提前获得信道信息,是不是能对发送策略有指导作用,并且有效的帮助我们提升通信系统的性能呢? 这里有一个例子,说明这一问题。假设有一车货物要从A地运到B地,有3条路可以选择,分别...
  • 第1章下行公共控制信道PDCCH简介 1.1下行公共控制信道PDCCH概述 PDCCH: Physical Downlink Common ...上行公共物理控制方面,NR和LTE系统中一样,只有PUCCH(Physical Uplink Control Channel)信道下行...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,401
精华内容 2,560
关键字:

在同一信道的同一时刻