diff --git a/tests/test-hello-protocol.cpp b/tests/test-hello-protocol.cpp
new file mode 100644
index 0000000..67bf272
--- /dev/null
+++ b/tests/test-hello-protocol.cpp
@@ -0,0 +1,121 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2014-2020,  The University of Memphis,
+ *                           Regents of the University of California,
+ *                           Arizona Board of Regents.
+ *
+ * This file is part of NLSR (Named-data Link State Routing).
+ * See AUTHORS.md for complete list of NLSR authors and contributors.
+ *
+ * NLSR is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NLSR is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE.  See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "hello-protocol.hpp"
+#include "nlsr.hpp"
+#include "test-common.hpp"
+
+namespace nlsr {
+namespace test {
+
+class HelloProtocolFixture : public UnitTestTimeFixture
+{
+public:
+  HelloProtocolFixture()
+    : face(m_ioService, m_keyChain, {true, true})
+    , conf(face, m_keyChain)
+    , confProcessor(conf)
+    , adjList(conf.getAdjacencyList())
+    , nlsr(face, m_keyChain, conf)
+    , helloProtocol(nlsr.m_helloProtocol)
+  {
+    ndn::FaceUri faceUri("udp4://10.0.0.1:6363");
+    Adjacent adj1(ACTIVE_NEIGHBOR, faceUri, 10, Adjacent::STATUS_ACTIVE, 0, 300);
+    adjList.insert(adj1);
+  }
+
+  int
+  checkHelloInterests(ndn::Name name)
+  {
+    int sent = 0;
+    for (const auto& i : face.sentInterests) {
+      if (name == i.getName().getPrefix(4)) {
+        sent++;
+      }
+    }
+    return sent;
+  }
+
+  void
+  checkHelloInterestTimeout()
+  {
+    helloProtocol.sendHelloInterest(ndn::Name(ACTIVE_NEIGHBOR));
+    this->advanceClocks(10_ms);
+    BOOST_CHECK_EQUAL(checkHelloInterests(ACTIVE_NEIGHBOR), 1);
+    this->advanceClocks(4_s);
+    BOOST_CHECK_EQUAL(checkHelloInterests(ACTIVE_NEIGHBOR), 2);
+    this->advanceClocks(4_s);
+    BOOST_CHECK_EQUAL(checkHelloInterests(ACTIVE_NEIGHBOR), 3);
+    if (conf.getHyperbolicState() == HYPERBOLIC_STATE_ON) {
+      BOOST_CHECK_EQUAL(nlsr.m_routingTable.m_isRouteCalculationScheduled, false);
+    }
+    else {
+      BOOST_CHECK_EQUAL(nlsr.m_lsdb.m_isBuildAdjLsaSheduled, false);
+    }
+    BOOST_CHECK_EQUAL(adjList.findAdjacent(ndn::Name(ACTIVE_NEIGHBOR))->getStatus(),
+                      Adjacent::STATUS_ACTIVE);
+
+    this->advanceClocks(4_s);
+    BOOST_CHECK_EQUAL(checkHelloInterests(ACTIVE_NEIGHBOR), 3);
+    if (conf.getHyperbolicState() == HYPERBOLIC_STATE_ON) {
+      BOOST_CHECK_EQUAL(nlsr.m_routingTable.m_isRouteCalculationScheduled, true);
+    }
+    else {
+      BOOST_CHECK_EQUAL(nlsr.m_lsdb.m_isBuildAdjLsaSheduled, true);
+    }
+    BOOST_CHECK_EQUAL(adjList.findAdjacent(ndn::Name(ACTIVE_NEIGHBOR))->getStatus(),
+                      Adjacent::STATUS_INACTIVE);
+  }
+
+public:
+  ndn::util::DummyClientFace face;
+  ConfParameter conf;
+  DummyConfFileProcessor confProcessor;
+  AdjacencyList& adjList;
+  Nlsr nlsr;
+  HelloProtocol& helloProtocol;
+  const std::string ACTIVE_NEIGHBOR = "/ndn/site/%C1.Router/router-active";
+};
+
+BOOST_FIXTURE_TEST_SUITE(HelloProtocol, HelloProtocolFixture)
+
+BOOST_AUTO_TEST_CASE(Basic)
+{
+  this->advanceClocks(10_s);
+  checkPrefixRegistered(face, "/ndn/site/%C1.Router/this-router/nlsr/INFO");
+  face.sentInterests.clear();
+}
+
+BOOST_AUTO_TEST_CASE(HelloInterestTimeoutLS) // #5139
+{
+  checkHelloInterestTimeout();
+}
+
+BOOST_AUTO_TEST_CASE(HelloInterestTimeoutHR) // #5139
+{
+  conf.setHyperbolicState(HYPERBOLIC_STATE_ON);
+  checkHelloInterestTimeout();
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace test
+} // namespace nlsr
\ No newline at end of file