IT Lab艾鍗學院技術Blog

2017年1月4日星期三

馬可夫鏈 (Markov Chain)

1) Random Variable X

2) Random Process (Stochastic Process) {X(t), t>=0} , 是一個Random Variable 的集合, (t可以是discrete time or continuous time)

3) Markov Process, 也是 Random Process,此Random Process {Xi,i=0,1,2....}是在描述狀態轉移的過程 (所有你會有一群狀態序列Chain), 但此系統的行為是chain中的節點，只和相鄰的節點有關，即你下一個狀態是什麼只取決你上一個狀態有關,而和先前的狀態無關 (此行為是是Markov property, 即Memory-less)

\Pr(X_{n+1}=j|X_0, X_1, \ldots, X_n=i)=\Pr(X_{n+1}=j|X_n=i)\, \forall n \ge1, i,j \in \mathrm{S}

a discrete-time Markov Process--> Markov chain(DTMC)

a continuous-time Markov process--> Markov chain (CTMC)

4) Renewal process : is a counting process in which the inter-arrival times are an iid random sequence

在講時間，事件發生的間隔時間為一個隨機變數Ti , 若Ti 彼'此為iid 則此counting process為renewal process。 (只看時間，不看狀態)

\Pr(\tau_{n+1}\le t|T_0, T_1, \ldots, T_n)=\Pr(\tau_{n+1}\le t)\, \forall n \ge1, \forall t\ge0

5) Markov Renewal Process

將 Markov process 再加上時間, 則狀態轉換和時間產生了關係。 Markov Renewal Process 共包含了2個隨機變數 {Xi,Ti}，狀態是一個隨機變數，時間也是一個隨機變數。也許我們想關心，在這個狀態待多久後會跳到下一個狀態。

Consider a state space

\mathrm{S}.

Consider a set of random variables

(X_n,T_n)

, where

T_{n}

are the jump times and

X_{n}

are the associated states in the Markov chain (see Figure). Let the inter-arrival time,

\tau_n=T_n-T_{n-1}

. Then the sequence

(X_n,T_n)

is called a Markov renewal process if

\Pr(\tau_{n+1}\le t, X_{n+1}=j|(X_0, T_0), (X_1, T_1),\ldots, (X_n=i, T_n))

=\Pr(\tau_{n+1}\le t, X_{n+1}=j|X_n=i)\, \forall n \ge1,t\ge0, i,j \in \mathrm{S}

6) Semi-Markov process

If we define a new stochastic process $Y_t:=X_n$ for $t \in [T_n,T_{n+1})$ , then the process $Y_{t}$ is called a semi-Markov process. Note the main difference between an MRP and a semi-Markov process is that the former is defined as a two-tuple of states and times, whereas the latter is the actual random process that evolves over time and any realisation of the process has a defined state for any given time. The entire process is not Markovian, i.e., memoryless, as happens in a continuous time Markov chain/process (CTMC). Instead the process is Markovian only at the specified jump instants. This is the rationale behind the name, Semi-Markov.^[1]^[2]^[3] (See also: hidden semi-Markov model.)

Semi-Markov process 和Markov process的差異是,

會進入到某一個狀態 Xn ,只會發生在特定的時間區間,而不是發生在所有的時間點，因此，Semi-Markov Process 其Markovian 特性 (即memory-less的特性), 只會在特定時間而已，而非任意時間區間) 。即在Xn狀態只有和上一個狀態有關。而會落在上一個狀態其時間點也是特定的。

(defined in the above bullet point) where all the holding times are exponentially distributed is called a CTMC.

Ergodic

A random process is ergodic if its time average is the same as its average over the probability space,

在某一段時間的平均, X/Ti 和整個時間的平均 X /T 是相同, 則稱為ergodic

Markov Model ( 所有狀能已知)

馬可夫模型是一連串事件(狀態)接續發生的機率
馬可夫鏈（英語：Markov chain），又稱離散時間馬可夫鏈（discrete-time Markov chain，縮寫為DTMC^[1]），因俄國數學家安德烈·馬可夫（俄語：Андрей Андреевич Марков）得名，為狀態空間中經過從一個狀態到另一個狀態的轉換的隨機過程。

A Markov chain is a stochastic process with the Markov property. The term "Markov chain" refers to the sequence of random variables such a process moves through, with the Markov property"memorylessness"). defining serial dependence only between adjacent periods (as in a "chain").

It can thus be used for describing systems that follow a chain of linked events, where what happens next depends only on the current state of the system.

已定義所有的狀態, 並有定義好從狀態 i 到各個狀態 j 的機率, 若共有N個狀態, 這就有一個矩陣描述每一個狀態彼此間的轉移的機率, ,這就狀態轉移機率矩陣 (State Transition probability matrix)

存在在一個狀態序列

常問的問題:

我們也許想知道, 原本在S0 狀態，經過T步後, 會落在那一個狀態? ( 這會需要知道 Pij : 狀態i 到 j 的機率)
S0-->S1-->S2, 一開始在S0走2步後, 出現在S2的機率為何?

Relation to other stochastic processes[edit]

A semi-Markov process (defined in the above bullet point) where all the holding times are exponentially distributed is called a CTMC. In other words, if the inter-arrival times are exponentially distributed and if the waiting time in a state and the next state reached are independent, we have a CTMC.
$\Pr(\tau _{n+1}\leq t,X_{n+1}=j|(X_{0},T_{0}),(X_{1},T_{1}),\ldots ,(X_{n}=i,T_{n}))=\Pr(\tau _{n+1}\leq t,X_{n+1}=j|X_{n}=i)$
$=\Pr(X_{n+1}=j|X_{n}=i)(1-e^{-\lambda _{i}t}),{\text{ for all }}n\geq 1,t\geq 0,i,j\in \mathrm {S}$
The sequence $X_{n}$ in the MRP is a discrete-time Markov chain. In other words, if the time variables are ignored in the MRP equation, we end up with a DTMC.
$\Pr(X_{n+1}=j|X_{0},X_{1},\ldots ,X_{n}=i)=\Pr(X_{n+1}=j|X_{n}=i)\,\forall n\geq 1,i,j\in \mathrm {S}$
If the sequence of $\tau$ s are independent and identically distributed, and if their distribution does not depend on the state $X_{n}$ , then the process is a renewal process. So, if the states are ignored and we have a chain of iid times, then we have a renewal process.
$\Pr(\tau _{n+1}\leq t|T_{0},T_{1},\ldots ,T_{n})=\Pr(\tau _{n+1}\leq t)\,\forall n\geq 1,\forall t\geq 0$
$事件發生的時間和狀態都無關(不論狀態是過去,現在或未來的狀態)$

Hidden Markov Model (存在未知狀態)

也許某些情況，我們無法或根本無法完整定義所有事件(狀態)的轉移機率矩陣 ,

圖來源: http://www.csie.ntnu.edu.tw/~u91029/HiddenMarkovModel.html#1

存在一個Hidden State ，不知道內部會怎麼選的機制, 而僅知道 S1,S2,S3狀態

在這個例子裡，有兩個事件的序列：一個是我觀察得到的；另一個是我看不到的，也就是對我來說是隱藏的，就是Hidden State。由於我知悉這兩個馬可夫鏈之間的關係，所以我便可以由其中一個馬可夫鏈的狀態，去預測另一個馬可夫鏈的狀態。而「隱馬可夫模型」，便是描述這樣的兩個序列的關係的統計模型。

HMM讓我們可以利用「看得到的」連續現象去探究、預測另一個「看不到的」連續現象。

隱藏馬可夫模型的特色就是：我們只看到了觀察序列（果），但是我們看不到狀態序列（因）；我們只看到了依序噴出的 T 個值，但是我們看不到一路走過的是哪 T 個狀態。

References:

http://www.csie.ntnu.edu.tw/~u91029/HiddenMarkovModel.html#1
https://en.wikipedia.org/wiki/Markov_renewal_process
http://www.waelde.com/pdf/SchummDissertationCh4.pdf

2016年12月30日星期五

Wi-Fi 與Zigbee 的MAC Algorithm

Zigbee 的MAC Algorithm:

(1) Binary Random Backoff
(2) Channel Idle > CCA (CW=2) ==> 如果CW減到0 則傳送否則重新再來過

CW=2 是一個固定值 , 表示idle 至少有CW以上的時間,才認為channel idle 才可以傳

若Binary Random Backoff 完後, channel仍不是idle (包含CW沒有減到0) 則再一次進行Binary Random Backoff

BP=random(0, 2^BE-1)

BP: Backoff Period
BE: Binary Exponent , 每次發生collision . BE都會增加 ,其初始值為3, 則第一次BP為random(0,7)
NB: backoff 次數限值

Wi-Fi 的MAC Algorithm (DCF)

DCF (Distributed Coordination Function)= CSMA/CA+ACK

程序:

(1) Channel Idle > DIFS ? ==> channel idle是否大於DIFS的期間,若否繼續偵側，直到大於DIFS。若大於DIFS, 則隨機選一個random backoff window, 並且每一個time slot減1, 當減到0時, 才能傳送。減1的動作只有在判斷channel 是Idle的狀態才會減1, 若channel是busy狀態, 則不減1 ("freeze Backoff window")

採用time backoff 機制讓其他人有機會可以取得medium來傳送。

(2) Binary Random Backoff ( 決定了CW的值 ) => 當CW減到0時, 就直接傳送不用管channel idle與否。若傳了之後是發生碰撞(沒有收到ACK則視為碰撞)，則此次傳輸沒有成功, 再重傳, 從(1)再來過。

CW=2 非固定值, CW=random(CWmin, 2^BE-1) 介於CWmin~CWmax中間,

CWmin------------ CW-------------------CWmax
CW=min(CWmax, CW)
CW=max(CWmin, CW)

若idle 長度至少有DIFS的長度才視為channel idle

----------------------------------------------------------

Wi-Fi vs Zigbee

Zigbee和Wi-Fi 都是利用 Time Backoff 來創造一個公平機會的Medium Access 機制
Zigbee 的CW是固定值, 而Wi-Fi CW是一個變數, Wi-Fi CW 其實是Zigbee 的BP, 兩者名稱相同, 但意思不同
Zigbee 評估 Channel Idle , 看CW, 而Wi-Fi 評估 Channel Idle , 看DIFS
Zigbee Backoff 的 BP會一直減1不管channel 是否idel或有人傳 , 而Wi-Fi Backoff 的 CW會減1但必須channel 是 idel狀態才能減1

CCA: Clear Channel Assessment

CW: Contention Window

DCF: Distributed Coordination Function

DIFS: DCF Inter Frame Space

References:

https://www.vocal.com/networking/802-11-distributed-coordination-function-dcf/

99.9% of the time Wireless is half duplex. There are experiments that can result in a "full duplex" wireless network but that's all lab-based and not real-world.

Full-duplex is what most wired connections use which means two devices can send and receive data at the same time and can also detect collisions straight away. via CSMA/CD

With Wireless the devices cannot send and receive simultaneously and they cannot sense collisions. Instead they use CSMA/CA to detect usage on the frequency to see if it is safe to transmit data. There are a large number of factors that can affect a wireless signal and interfere with it which results in lower throughput.

2016年12月23日星期五

Raspberry Pi SD卡從8G變16G

從8G SD卡變成16G SD 卡, 要如何resize Partition

原本8G:

fdisk -h

Device Boot Start End Sectors Size Id Type
/dev/mmcblk0p1 8192 137215 129024 63M c W95 FAT32 (LBA)
/dev/mmcblk0p2 137216 15564799 15427584 7.4G 83 Linux

首先，您需要使用fdisk更改分割表要刪除現有的分區條目，然後創建一個新的分區吃滿整個可用空間。

Manually resizing the SD card on Raspberry Pi

You can also resize the partitions of the SD card that your Pi is running on.

First you need to change the partition table with fdisk. You need to remove the existing partition entries and then create a single new partition than takes the whole free space of the disk. This will only change the partition table, not the partitions data on disk.

The start of the new partition needs to be aligned with the old partition!

Start fdisk:

sudo fdisk /dev/mmcblk0

Then delete partitions with d and create a new with n. You can view the existing table with p.

p to see the current start of the main partition
d, 3 to delete the swap partition
d, 2 to delete the main partition
n p 2 to create a new primary partition, next you need to enter the start of the old main partition and then the size (enter for complete SD card). The main partition on the Debian image from 2012-04-19 starts at 157696, but the start of your partition might be different. Check the p output!
w write the new partition table

Now you need to reboot:

 sudo shutdown -r now

After the reboot you need to resize the filesystem on the partition. The resize2fs command will resize your filesystem to the new size from the changed partition table.

sudo resize2fs /dev/mmcblk0p2

This will take a few minutes, depending on the size and speed of your SD card.

When it is done, you can check the new size with:

df -h

2016年12月11日星期日

物聯網應用層通訊協定標準比較 CoAP vs MQTT

機器對機器 (Machine-to-Machine， M2M)通訊是物聯網的一個重要運作概念。隨著物聯網的應用日益興盛，M2M流量會持續增加，故針對M2M Traffic特徵及其應用，M2M通訊技術應運而生。由於物聯網架構下，感測節點本身多半採用MCU且以電池供電，故這些新的M2M協定必須考量在有限的硬體能力及功耗等條件下，使得M2M Traffic在進行網路傳輸時，有較高的Throughput、低延遲、低電力耗損，甚至提供不同的 QoS (Quality of Service)。

目前各家提供連結物聯網裝置的雲端資料服務平台，包含
AWS IoT(https://aws.amazon.com/tw/iot/)、Evrythng(https://evrythng.com/)、Xively(https://www.xively.com/)、ThingSpeak(https://thingspeak.com/)、ThingWorx(https://www.thingworx.com/)等及晶片廠提供的雲平台，如聯發科的MCS(https://mcs.mediatek.com/)、ARM mbed Device Connector(https://connector.mbed.com/)等，都廣泛支援CoAP及MQTT協定，故將選擇此兩種協定來進行說明與比較。

M2M協定介紹

CoAP

CoAP(The Constrained Application Protocol) 目前已是IETF標準(RFC 7252) ，提出一個類似HTTP/TCP設計，但是屬於輕量版的HTTP/UDP，使得其有利於感測節點進行網路傳輸。

CoAP主要特點:

CoAP同HTTP一樣具有REST(Representational State Transfer)設計風格，也支援GET/PUT/POST/DELETE及URIs的請求方式。
CoAP是主從(Client/Server)架構，感測節點多半為CoAP Client 上傳(PUT)感測資訊或節點狀態到CoAP Server。CoAP Server使用UDP (port: 5683)，對於資料是否要重傳或傳送順序(Reordering) 全交由上層應用層來決定，對於資源有限的MCU則不需要TCP協定實作。感測節點多半為CoAP Client, 因為感測節點通常是On-Off (Duty-cycled)工作模式, 只有醒來時才工作以節省能耗。若反過感測節點為CoAP Server, 則由Cloud 作為CoAP Client , 執行Get 以存取節點狀態資訊。
CoAP採用二進位整數格式且封包標頭4 個byte而非HTTP使用字串格式(ASCII code)，所以封包傳送時的額外負擔小且不必像HTTP一樣得進行耗時的字串解析處理。
CoAP QoS : CoAP訊息分為Confirmable或Non-Confirmable。Confirmable要求接收端須回送ACK，若沒有收到ACK則重送一次。若送的是Non-Confirmable訊息，則送出端不在乎接收端是否收到。
CoAP使用DTLS (Datagram Transport Layer Security) 進行加密
通知機制: CoAP擴展了HTTP GET，加入了一個observe flag，用來主動回報所observe到的狀態，而不必像原本HTTP需要一直polling,如此可節省不必要的通訊。實作上MCU 為CoAP Client, 一旦狀態改變時主動發出CoAP GET 即可將資料丟到server
NAT Issue: 若感測節點在NAT後方，則必須一開始先送出請求到外部，使路由器可以接受來自外面CoAP Client的請求，例如請求資源清單。

MQTT

MQTT（Message Queuing Telemetry Transport）是IBM開發的一個即時通訊協定，2010年IBM釋出免授權版本(v3.1)。MQTT是機器對機器（M2M）物聯網的連接協定。它被設計成一個非常輕量級的發布/訂閱消息傳輸。對於感測節點擁有很少的記憶體和或網路頻寬很小的情況下， MQTT非常適合。MQTT已經是ISO（ISO / IEC 20922：2016）和OASIS標準。另外，Facebook Messenger即是採用MQTT協定。

MQTT的主要特點:

1. 訊息傳遞為Publish/Subscribe的方式，以提供一對多的訊息分派

Client B及Client C先向Broker訂閱(Subscribe)一個Temperature主題, 而Client A向Broker發佈(Publish)在該主題Temperature發佈訊息(22.5)，則Client B及Client C 都會收到此訊息。

使用TCP port 1883作為通訊傳輸層
Header固定長度為2 byte，因此可以減少封包傳送時的額外負載，並減少所需的網路頻寬
Publish 和Broker 中間發生異常斷線時，會使用最後遺囑(Last Will )的機制，通知所有Subscriber
3種傳送服務QoS (0,1,2)：

Publisher <----> Broker <----> Subscriber

兩段所設定的QoS ，其作用的結果取兩段最小QoS值

1.) QoS=0 "At most once": 最多送一次 ,但可能沒收到，"Fire and Forget"

• Publisher不會Re-Publish訊息給Broker。因為使用底層是TCP, 所以Broker 一定會收到，而剩下的問題為 Broker 和Subscriber 兩者間的傳輸問題。

• 這適合應用在環境感測， Subscriber並不會在意Publisher是否會再重送，因為下一次的資料取樣很快就會再丟出來

2.) QoS=1 "At least once": 可能收到一次以上 >=1

• 如果時間內Publisher沒收到來自Broker的PUBACK, Publisher會Re-Publish訊息。如此Broker很有能收到2次以的重覆的訊息，因此Subscriber 就可能跟著會重覆收到相同訊息。

3.) QoS=2 "Exactly once":只會收到一次=1。

• 為避免像QoS 1, Subscriber有可能收到重覆的訊息。因此Publisher 會有Message ID, 使得Broker 能夠判別這是Publisher 所送的重覆資料, 才不致於送給Subscriber重複的資料。

• 這適合用在計費系統，系統只要有重複收到資料、或是資料遺失狀況發生，就會造成系統錯誤。

CoAP vs MQTT 比較

都是公開標準且都是基於IP層的協定
封包標頭小且採用binary格式
CoAP屬於一對一通訊，MQTT則是多對多
若考慮感測節點在NAT後方的情況，由於MQTT的架構因為有中央broker的角色，MQTT Client本來就持續連接在broker，所以可以直接推播訊息，沒有NAT問題。然而CoAP Client要取得位於NAT後方的感測節點資料，則須要在路由器上設上設定virtual server或port forwarding之類才能使用，不然就必須另外有第三方伺服器存在，讓感測節點先連出才行

Raspberry Pico W 使用 MQTT publish

References:


 
Observing Resources in the Constrained Application Protocol (CoAP)

2016年11月18日星期五

LPWAN 長距離低功耗通信技術 : NB-IoT vs LoRa

IoT 遠距離通信技術 : NB-IoT、LoRa均為 LPWAN (Low Power Wide Area Network), 主要應用都在智慧城市、智慧交通(如停車場)管理，智能電錶、水錶抄表、智能農業等低數據量的採集。

WiFi和BTLE主要應用於個人設備相關的應用。蜂窩技術主要應用於需要高數據吞吐量，以及需要供電的應用場景。LPWAN的應用場景包括：長電池壽命，並且傳感器和應用在長距離下，只需要每小時只要傳遞幾次數據。

「NB-IOT LTE-M」的圖片搜尋結果

	NB-IoT	LoRa

聯盟	3GPP 2016年6月標準提出	2013年8月，Semtech公司發表一顆Lora 晶片 LoRa Alliance (2015年3月) IBM主導
技術特點	蜂巢同步協議 (節點必須定期地連到基地台)	線性展頻非同步協議
網路佈署	運用原本的4G/LTE基地台(升級現有)	獨立建構自家的LoRa網路, 節點構通都必須同屬LoRa網路 (不同於Internet門派)
頻段	電信營運商頻段 1GHz以下的授權頻段, 建置成本高	150MHz~1GHz的非授權頻段, 建置成本低
傳輸距離		1~20Km
速率	<100kbps	<50kbps
連接數量	200k/cell	200k~300k/hub
終端電池工作時間	約10年	約10年
模組成本	約$5~$10	約$5
	電信營運商	可由企業自行搭建