作者：泰一
來源：
碼神說公衆号- 導讀
- 指數平滑
- 一次指數平滑法（Single Exponential Smoothing）
- 指數平滑系數（Smoothing Coeff）
- 最小二乘法求解線性回歸
- 線性回歸（Linear Regression）
- 最小二乘法（Least Square）
- 源碼分析
- Trendline 濾波器參數
- LinearFitSlope 函數
- Update 函數
- 測試用例
上一篇介紹了包組時間差的相關概念與計算過程，在
ComputeDeltas
函數中，我們最終得到了包組的發送時間差
send_delta_ms
和到達時間差
arrival_delta_ms
。
本篇将介紹 WebRTC 的
Trendline
濾波器如何根據計算出來的發送時間差與到達時間差去評估最終的延遲梯度的趨勢值，在此之前，需要了解指數平滑與線性回歸的相關概念。
指數平滑法（Exponential Smoothing） 是在移動平均法基礎上發展起來的一種時間序列分析預測法，它是通過計算指數平滑值，配合一定的時間序列預測模型對現象的未來進行預測。其原理是任一期的指數平滑值都是本期實際觀察值與前一期指數平滑值的權重平均，是以也是一種特殊的權重平均法。一次指數平滑法預測公式如下：
再來看百度百科對指數平滑法 [1] 的一段描述：
簡單的全期平均法是對時間數列的過去資料一個不漏地全部加以同等利用；移動平均法則不考慮較遠期的資料，并在權重移動平均法中給予近期資料更大的權重；而指數平滑法則相容了全期平均和移動平均所長，不舍棄過去的資料，但是僅給予逐漸減弱的影響程度，即随着資料的遠離，賦予逐漸收斂為零的權數。
為了加深對上面這段話的了解，我們把一次指數平滑公式進行變形：公式 (1) 中，最後的 表示如下：
将公式 (2) 代入公式 (1)，整理得：
同理，可以将 的表示代入公式 (3)，最後得到的通用公式如下：
觀察公式 (4)，可知：
指數平滑系數的選擇的原則如下：
- 如果時間序列波動不大，比較平穩，則平滑系數應取小一點，以減少修正幅度，使預測模型能包含較長時間序列的資訊。
- 如果時間序列具有迅速且明顯的變動傾向，則平滑系數應取大一點，以使預測模型靈敏度高些，以便迅速跟上資料的變化。
在 WebRTC 發送端基于延遲的擁塞控制中，累計延遲梯度的指數平滑系數為 0.9。
如果預測的變量是連續的，我們稱其為回歸。回歸分析中，如果隻包括一個自變量和一個因變量，且二者的關系可用一條直線近似表示，這種回歸分析稱為一進制線性回歸或者簡單線性回歸。線性回歸過程主要解決的就是如何通過樣本來擷取最佳的拟合線。
也稱最小平方法 [2]，是一種數學優化技術。它通過最小化誤差的平方和尋找資料的最佳函數比對。
簡單線性回歸最常用的方法便是最小二乘法，其數學推導過程如下：
基于 WebRTC M71 版本。
Trendline 濾波器的三個重要參數分别是：視窗大小、平滑系數、延遲梯度趨勢的增益。
視窗大小決定收到多少包組之後開始計算延遲梯度趨勢；平滑系數用于累計延遲梯度的一次指數平滑計算；對累計延遲梯度平滑值進行最小二乘法線性回歸之後求得延遲梯度趨勢，會乘以增益并和門檻值作比較，以檢測帶寬使用狀态。下面是 WebRTC 中這三個參數的預設值。
constexprsize_t
kDefaultTrendlineWindowSize = 20;
constexprdouble
kDefaultTrendlineSmoothingCoeff = 0.9;
constexprdouble
kDefaultTrendlineThresholdGain = 4.0; 該函數使用最小二乘法求解線性回歸，輸入
window_size_
個樣本點（arrival_time_ms, smoothed_delay），輸出延遲梯度變化趨勢的拟合直線斜率 trendline_slope。
absl::optional<double> LinearFitSlope(
const std::deque<std::pair<double, double>>& points); 求解過程完全參照公式 (7)。
該函數輸入包組間到達時間差與發送時間差以及包組的到達時間，并估計延遲梯度的趨勢。
class TrendlineEstimator {
public:
void Update(
double recv_delta_ms,
double send_delta_ms,
int64_t arrival_time_ms);
}; 該函數是 Trendline 濾波器的核心實作，包括：
- 計算延遲梯度
- 計算累計延遲梯度的一次指數平滑值
- 最小二乘法線性回歸求延遲梯度趨勢斜率
- 檢測帶寬使用狀态，比如是否過載
- 更新延遲梯度趨勢動态門檻值
本篇介紹前 3 個實作過程。
constdouble delta_ms =
recv_delta_ms - send_delta_ms; 上一篇已經介紹過延遲梯度的計算公式：
d(i) = inter-arrival - inter-depature 那麼延遲梯度為何能作為網絡擁塞的标志呢？
當網絡沒有擁塞，延遲梯度：t2 - t1- (T2 - T1) = 0，如下圖所示。
網絡正常
當網絡存在擁塞，資料包經過 router 節點時經曆排隊等待，導緻到達時間比原本要晚，延遲梯度：t2 - t1- (T2 - T1) > 0，如下圖所示。
網絡擁塞
是以，延遲梯度可以作為網絡擁塞的訓示。把一段時間内的資料包組的延遲梯度累加、平滑、回歸，最終得到延遲梯度的趨勢，這就是 Trendline 濾波器要做的事情。
- 累計延遲梯度一次指數平滑
// Exponential backoff filter.
accumulated_delay_ += delta_ms;
smoothed_delay_ = smoothing_coef_ * smoothed_delay_ +
(1 - smoothing_coef_) * accumulated_delay_; 注意，計算一次指數平滑值的公式為:
實際觀測值前面的系數為:
而上述源碼的計算公式的實際觀測值
accumulated_delay_
的平滑系數為:
形式不一，但本質不變。
smoothing_coef_
取 0.9，那麼
accumulated_delay_
前的平滑系數為 0.1，這意味着新的延遲梯度觀測值的變化對平滑值的影響較小，減少了修正幅度。
上面提到的指數平滑系數的選擇的原則：當時間序列波動不大，比較平穩的時候會選擇較小的系數。
累計延遲梯度平滑值
smoothed_delay_
計算出來之後将作為 y 軸的資料與作為 x 軸資料的到達時間序列存入隊列。當樣本點的數量達到濾波器的視窗大小，開始使用最小二乘法求解線性回歸，
LinearFitSlope
函數實作了這個過程。
// Simple linear regression.
// Update trend_ if it is possible to fit a line to the data. The delay
// trend can be seen as an estimate of (send_rate - capacity)/capacity.
delay_hist_.push_back(std::make_pair(
static_cast<double>(arrival_time_ms - first_arrival_time_ms_),
smoothed_delay_));
trend = LinearFitSlope(delay_hist_).value_or(trend); 最終得到了線性回歸的解：延遲梯度的變化趨勢 trend，其實就是很多離散的樣本點的拟合直線斜率。這個預測的斜率值
trend
可以表征網絡的擁塞程度（網絡緩沖區，即路由器資料包排隊的消漲情況）：
- 0 < trend < 1，資料包延遲不斷加大，路由器緩沖隊列長度持續增加，直到網絡緩沖區被填滿。
- trend == 0，資料包延遲恒定，路由器緩沖區隊列長度不變。
- trend < 0，資料包延遲不斷減少，路由器緩沖區隊列長度不斷減少，直到隊列為空。
下面進行簡單的測試，将 Trendline 濾波器視窗設定為 20，平滑系數設定為 0.9，增益設定為 1。按照 slope = 0.5 的期望延遲梯度趨勢斜率構造了 41 個包組，測試輸出如下：
測試輸出.png
當樣本點到達視窗大小 20 時，開始線性回歸求解延遲梯度趨勢斜率，x 代表包組到達時間與首個包組到達時間的內插補點，y 代表延遲梯度平滑值。可以看到，随着樣本數量增多，斜率值逼近期望值 0.5。
為了有更直覺的認識，我将測試資料導入 Minitab Express，進行一次指數平滑計算，如下圖：
一次指數平滑
可以看到，一次指數平滑法進行預測，預測趨勢與實際變動趨勢一緻，但預測值比實際值滞後，這是指數平滑法的一個缺點。一次指數平滑法優點在于它在計算中将所有的觀察值考慮在内，對各期按時期的遠近賦予不同的權重，使預測值更接近實際觀察值。
繼續對計算完成的延遲梯度的平滑值進行簡單的線性回歸，如下圖：
簡單線性回歸
回歸公式（Regression Equation）：C3 = − 27.641 + 0.416902C1，求得的拟合直線的斜率為 0.416902，加大樣本的資料量，線性回歸模型的預測會更加接近 0.5。
至此，延遲梯度趨勢的計算過程介紹完畢，這個趨勢值要與動态門檻值進行比較，以檢測網絡帶寬使用是否過載，下一篇會介紹這個過程，感謝閱讀。
參考資料
[1]指數平滑法:
https://baike.baidu.com/item/指數平滑法
[2]最小二乘法:
最小二乘法 / 2522346?fr=aladdin
「視訊雲技術」你最值得關注的音視訊技術公衆号，每周推送來自阿裡雲一線的實踐技術文章，在這裡與音視訊領域一流工程師交流切磋。